Sous-graphes connexes

Soit $G$ un graphe connexe avec au moins 2 sommets. Pour $s$ sommet de $G$ , $G \setminus \{s\}$ désigne le sous-graphe obtenu à partir de $G$ en retirant le sommet $s$ ainsi que toutes ses arêtes.

Montrer qu’il existe 2 sommets distincts $s_{1}$ et $s_{2}$ tels que les sous-graphes $G \setminus \{s_{1}\}$ et $G \setminus \{s_{2}\}$ soient tous deux connexes.

I solved itMark it done Add to my listKeep it in your list

I like this problem0 likes

Hints

Hint 1

Open this only if you want a small nudge before looking at the solutions.

Solutions

Reveal solutionsAre you sure? Give it a try first.

Solution by David L.

Discussions0 useful votes

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$ .

Report