next up previous
suivant: Démonstration monter: Démonstration de l'équivalence des précédent: Démonstration de l'équivalence des

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.

Bruno Garcia 2000-12-17