Assez d'arêtes force la connexité

Par contraposée, supposons $G$ non connexe. Ses sommets se répartissent alors en deux paquets non vides sans aucune arête entre eux, disons de tailles $k$ et $n-k$ avec $1\le k\le n-1$. Toutes les arêtes sont internes à un paquet, donc

$$m\le \left(\genfrac{}{}{0ex}{}{k}{2}\right)+\left(\genfrac{}{}{0ex}{}{n-k}{2}\right).$$

Ce majorant est maximal aux extrémités. La fonction $k\mapsto \left(\genfrac{}{}{0ex}{}{k}{2}\right)+\left(\genfrac{}{}{0ex}{}{n-k}{2}\right)$ est convexe et symétrique en $k\leftrightarrow n-k$ ; son maximum sur $[[1,n-1]]$ est atteint en $k=1$ (ou $k=n-1$) et vaut $\left(\genfrac{}{}{0ex}{}{1}{2}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$.

Donc un graphe non connexe a au plus $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ arêtes. Par contraposée, plus de $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ arêtes entraîne la connexité.

Le majorant est atteint : $K_{n-1}$ auquel on ajoute un sommet isolé a exactement $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ arêtes et n'est pas connexe. Le seuil est donc optimal — un de moins ne suffirait pas.