Sous-graphes connexes

Soit $C = s_1 - \dots - s_k$ un chemin de longueur maximale ne passant jamais 2 fois par le même sommet.
Comme $G$ est connexe et possède au moins 2 sommets, on a $s_1 \neq s_{k}$.
Montrons que $G \setminus \{s_{1}\}$ est connexe, ce qui montrera par un raisonnement analogue que $G \setminus \{s_{k}\}$ est connexe.

Soit $s$ et $t$ des sommets de $G \setminus \{s_{1}\}$ et soit $s - \dots - t$ un chemin les reliant dans $G$.

• Si le chemin ne passe pas par $s_{1}$ alors il existe toujours dans $G \setminus \{s_{1}\}$.
• Si le chemin passe par $s_{1}$, alors chaque passage par $s_{1}$ est de la forme $s_{i} - s_{1} - s_{j}$ (avec $i,j \neq 1$). En effet, par maximalité de $C$ tous les voisins de $s_{1}$ sont dans $C$. Le chemin peut alors être modifié pour éviter de passer par $s_{1}$ en suivant le parcours de $C$ pour aller de $s_{i}$ à $s_{j}$, ce qui nous donne un chemin de $G \setminus \{s_{1}\}$ reliant $s$ et $t$.