Démonstration $3 \:\Rightarrow\: 1$

Supposons que $H$ soit non connexe. Il possède donc au moins 2 composantes connexes. En appliquant la règle de construction numéro 2, il est possible d'ajouter un arc sans créer de cycle, ce qui entraîne une contradiction. Donc, $H$ est connexe et sans cycle, ce qui entraîne $m\,=\,n-1$. Moralité : un arbre est un graphe connexe et sans cycle qui possède exactement $n-1$ arcs.