Un graphe connexe a au moins $n-1$ arêtes

Construisons un ordre. Partons d'un sommet quelconque $v_1$ et posons $S_1=\{v_1\}$. Tant que $S_i$ ne contient pas tous les sommets, la connexité fournit une arête entre $S_i$ et son complémentaire — sinon aucun chemin ne sortirait de $S_i$, et $G$ ne serait pas connexe. Choisissons-en une, notons $v_{i+1}$ son extrémité extérieure et posons $S_{i+1}=S_i\cup \{v_{i+1}\}$.

Le procédé s'arrête après avoir atteint les $n$ sommets, et il a désigné $n-1$ arêtes : une à chaque étape, de $S_1$ à $S_n$.

Elles sont deux à deux distinctes : celle de l'étape $i$ a pour extrémité $v_{i+1}$, qui n'appartenait à aucun $S_j$ avec $j\le i$. Donc $G$ possède au moins $n-1$ arêtes.

Le minorant est atteint : un graphe connexe à exactement $n-1$ arêtes est un arbre, et les arêtes désignées ci-dessus en forment un — c'est un arbre couvrant de $G$.