1. Si le chemin n'est pas simple, il contient un sommet répété. C'est-à-dire qu'il existe un sous-chemin t = s_i → s_i+1 → … → s_i+k = t (k > 1). Le nouveau chemin s = s₁ → … → s_i → s_i+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).
   
   
2. 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 s₁, s₂ avec s₁ ↔ s₂. Le chemin s₁ ↔ s₂ ↔ s₁ contient l'arc s₁ ↔ s₂ deux fois et n'est donc pas un cycle.
   
   
3. 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 T₁ et T₂ (sinon un sous-arbre contiendrait un cycle). Un tel cycle contient nécessairement un « passage » de T₁ vers T₂ (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 u₁ et u₂, reliés par un arc, et tel que u₁ ∈ T₁ et u₂ ∈ T₂. Or, l'arc u₁ → u₂ ne peut appartenir ni à T₁, ni à T₂ (ni à aucun autre T_i, ni relier s à un de ses fils), ce n'est donc pas un arc de T, contradiction.