msleziak.com

Dokážte, že ak graf na $n$ vrcholoch má aspoň $\binom{n-1}2+1$ hrán, tak je súvislý. Ukážte na príklade, že $\binom{n-1}2$ hrán nestačí.

Sporom. Predpokladajme, že graf by bol nesúvislý. Potom obsahuje aspoň 2 komponenty súvislosti, čiže vrcholy môžeme rozdeliť na 2 neprázdne časti, ktoré nespája žiadna hrana. Nech počet vrcholov v jednej časti je $k$, v druhej z nich potom musí byť $n-k$ vrcholov. Maximálny počet hrán je preto
$$\binom k2+\binom {n-k}2.$$
Stačí nám teda ukázať, že pre ľubovoľné $k>1$ platí $$\binom k2+\binom{n-k}2\leq \binom{n-1}2.$$

Uvedomme si, že platí
$$\binom k2= \frac{k(k-1)}2= 1+2+\ldots+(k-1).$$
Z toho máme
\begin{align*}
\binom k2+\binom {n-k}2=&1+2+\ldots+(k-1)+ 1+2+\ldots+(n-k-1)\leq\\
&1+2+\ldots+(k-1)+ k+(k+1)+\ldots+(n-2)=\binom{n-1}2.
\end{align*}

Tým je vyriešená prvá časť úlohy. Príklad grafu na $n$ vrcholoch, ktorý má $\binom{n-1}2$ hrán a nie je súvislý dostaneme tak, že ku $K_{n-1}$ pridáme 1 izolovaný vrchol.

Pridám ešte dve linky týkajúce sa tejto istej úlohy: https://math.stackexchange.com/q/34212 a https://math.stackexchange.com/q/1225511
K nerovnosti týkajúcej sa binomických koeficientov: https://math.stackexchange.com/q/3005453