Les arbres, preuve du théorème

Parcours de graphes · niveau 3 (difficile)

Énoncé

Démontrer l'équivalence entre (i) connexe sans cycle, et (ii) connexe à $n - 1$ arêtes.

On sait que dans tout graphe connexe à $n$ sommets, il y a au moins $n - 1$ arêtes (démontré par la construction de l'arbre de parcours qui utilise exactement $n - 1$ arêtes pour découvrir les $n - 1$ sommets depuis la source).
On sait également que tout graphe acyclique à $n$ sommets contient au plus $n - 1$ arêtes.
Donc, si un graphe est à la fois connexe et sans cycle (i), le nombre d'arêtes $m$ doit satisfaire $n - 1 \leq m \leq n - 1$ , soit $m = n - 1$ arêtes (ii).
Inversement, si un graphe est connexe avec $n - 1$ arêtes (ii) : s'il contenait un cycle, on pourrait enlever une arête de ce cycle sans détruire la connexité. On obtiendrait alors un graphe connexe à $n - 2$ arêtes, ce qui contredit le fait qu'un graphe connexe possède au moins $n - 1$ arêtes. Donc le graphe est nécessairement acyclique (i).