Un arbre a exactement $n-1$ arêtes

1. La démonstration, par récurrence forte sur $n$.

Base : $n=1$. Un seul sommet, pas d'arête possible sans boucle — et une boucle est un cycle. Donc $m=0=n-1$.

Hérédité. Soit $T$ un arbre à $n\ge 2$ sommets.

Étape a : $T$ possède une feuille, c'est-à-dire un sommet de degré $1$. Considérons un chemin de longueur maximale parmi ceux qui ne répètent aucun sommet : $s_0,s_1,\dots ,s_k$. Il en existe, car ces chemins sont en nombre fini et il y en a au moins un — un sommet isolé est un chemin de longueur $0$ —, et $k\ge 1$ par connexité puisque $n\ge 2$. Le sommet $s_0$ n'a pas d'autre voisin que $s_1$ : un voisin $w\ne s_1$ serait soit hors du chemin, et l'on rallongerait le chemin, contredisant la maximalité ; soit un $s_i$ avec $i\ge 2$, et $s_0,s_1,\dots ,s_i,s_0$ serait un cycle. De plus $d(s_0)\ge 1$ par connexité ($n\ge 2$). Donc $d(s_0)=1$.

Étape b : retirons $s_0$ et son unique arête. Le graphe obtenu $T^{\prime }$ a $n-1$ sommets ; il reste acyclique — on n'ajoute rien —, et il reste connexe, car tout chemin entre deux sommets de $T^{\prime }$ qui passerait par $s_0$ y entrerait et en sortirait par la même arête, ce qui est impossible dans un chemin. $T^{\prime }$ est donc un arbre, et par hypothèse de récurrence il a $n-2$ arêtes. D'où $m(T)=n-2+1=n-1$.

2. La réciproque est fausse, et le contre-exemple est instructif : prenons un triangle $\{a,b,c\}$ plus un sommet isolé $d$. On a $n=4$ et $m=3=n-1$, et ce n'est ni connexe ni acyclique.

Mais deux réciproques partielles tiennent, et elles sont la manière normale d'employer ce résultat. Pour un graphe à $n$ sommets et $n-1$ arêtes :

• connexe $⟹$ arbre : s'il avait un cycle, on pourrait retirer une arête du cycle sans rompre la connexité, obtenant un graphe connexe à $n-2$ arêtes ; or un graphe connexe a au moins $n-1$ arêtes, contradiction ;
• acyclique $⟹$ arbre : une forêt à $n$ sommets et $c$ composantes a $n-c$ arêtes — appliquer le point 1 à chaque composante —, donc $c=1$.

La formulation à retenir : parmi les graphes à $n$ sommets, « connexe », « acyclique » et « $n-1$ arêtes » sont trois conditions dont deux quelconques entraînent la troisième. C'est la caractérisation qu'on emploie en pratique : pour vérifier qu'un graphe est un arbre, on compte ses arêtes et on teste une seule des deux autres propriétés — l'une des deux suffit, et le comptage est en $O(m)$.

Ce résultat sert immédiatement au chapitre chap:parcours : un parcours en profondeur d'un graphe connexe produit un arbre couvrant, et le comptage $n-1$ est ce qui garantit que l'on a bien un arbre et non une forêt.