-
Si le chemin n'est pas simple, il contient un sommet répété.
C'est-à-dire qu'il existe un sous-chemin t = si → si+1 → …
→ si+k = t (k > 1).
Le nouveau chemin s = s1 → … → si → si+k+1 →
… → s' est de
longueur strictement inférieure au chemin initial.
En itérant le procédé on obtient un chemin simple (c'est une preuve
par récurrence un peu rapide).
- Le procédé itératif précédent s'applique encore, il produira un chemin
de s à s dont tous les sommets « intérieurs » sont deux à deux
distincts et distincts de s.
Dans un graphe orienté la condition « sommets deux à deux
distincts » entraîne que tous les arcs du chemin sont deux à deux
distincts. On a donc produit un cycle.
Ce n'est plus vrai dans un graphe non-orienté.
Considérer le graphe s1, s2 avec s1 ↔ s2.
Le chemin s1 ↔ s2 ↔ s1 contient l'arc s1 ↔ s2 deux
fois et n'est donc pas un cycle.
- Par induction évidemment.
Il faut préciser un peu la définition en ajoutant que les sommets des
sous-arbres sont tous deux à deux distincts et distincts de la racine.
Un sommet solitaire ne permet aucun chemin et donc aucun cycle.
Si l'arbre T contient un cycle, ce cycle contient
des sommets de deux sous-arbres distincts, disons T1 et T2
(sinon un sous-arbre contiendrait un cycle).
Un tel cycle contient nécessairement un « passage » de T1
vers T2 (et ceci même si le cycle passe par la racine, ce qui est à
priori possible dans le cas non-orienté).
Plus précisément, il existe deux sommets u1 et u2, reliés
par un arc, et tel que
u1 ∈ T1 et u2 ∈ T2.
Or, l'arc u1 → u2 ne peut appartenir ni à T1, ni à T2 (ni
à aucun autre Ti, ni relier s à un de ses fils), ce
n'est donc pas un arc de T, contradiction.