Démonstration de l'équivalence des définitions sur les arbres

La démonstration de l'équivalence de ces propositions nécessite un théorème intermédiaire.

La démonstration de ce théorème se fait de manière constructive. En effet, considérons un graphe $G\,=\,\left\{X,\,E\right\}$, $\vert X\vert=n$ dont l'on retire tous les arcs. On ajoute alors les arcs 1 par 1. A un instant donné, la situation peut être telle que représentée par la figure (2.1).

Figure 2.1: Construction d'un arbre : situation de base

Lorsque l'on rajoute un arc, 2 cas peuvent se présenter :

1. L'arc réunit 2 sommets de la même composante connexe (2.2.a).
   • Le nombre de composantes connexes du graphe ne change pas
   • On crée un cycle dans la composante connexe
2. L'arc réunit 2 sommets appartenant à des composantes connexes différentes (2.2.b).
   • Le nombre de composantes connexes diminue de 1
   • On ne rajoute pas de cycle dans le graphe

   Figure 2.2: Construction d'un arbre : opérations élémentaires

   
   Appliquons ce principe de construction à la démonstration du théorème précédent. Si l'on désire que le graphe soit sans cycle, il nous faut procéder par la deuxième méthode d'ajout d'arc. Initialement, comme il n'y a pas d'arcs, il y a $n$ composantes connexes. A chaque ajout d'arc, le nombre de composantes connexes diminue de 1 unité. Après avoir ajouté $n-1$ arcs par cette méthode, il ne reste qu'une seule composante connexe, le graphe est donc connexe. Si maintenant, l'on construit un graphe par l'un ou l'autre principe de construction, il faut ajouter au moins (n-1) arcs avant d'obtenir une seule composante et donc un graphe connexe. D'où la seconde partie du théorème. En vertu du premier principe de construction, tout ajout d'arc rajoutera un cycle, ce qui démontre la première partie du théorème. Une fois le théorème démontré, les implications suivantes sont évidentes :
   $$\left\{ \begin{array}{@{(}l@{)}@{\:\Rightarrow\:}@{(}r@{)}... ... 1 \\ 0 & 2 \\ 1 & 4 \\ 2 & 3 \end{array} \right.$$
   Pour démontrer l'équivalence des propriétés sur les arbres, nous allons créer la boucle d'implications suivante (les implications non encore démontrées sont en gras) :
   $$\left\{ \begin{array}{@{(}l@{)}@{\:\Rightarrow\:}@{(}r@{)}... ...f{5} \\ \mathbf{5} & \mathbf{0} \\ \end{array} \right.$$