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

Démonstration $ 4 \:\Rightarrow\: 5$

Supposons qu'il existe deux chaînes distinctes permettant de joindre une paire de sommets $ (i,\,j)$. Alors, il existe au moins une arête $ (k,\,l)$ appartenant à la première chaîne mais pas à la seconde. Supprimons cet arc, il existe encore une chaîne permettant de joindre $ i$ à $ j$. En outre, si $ (i,\,j)$ est relié par une chaîne contenant l'arête $ (k,\,l)$, on peut remplacer l'arête par une chaîne pour établir la connexité. Le graphe est toujours connexe après suppression d'un arc ce qui contredit la proposition $ 4$.

Bruno Garcia 2000-12-17