Connected subgraphs

Let $G$ be a connected undirected graph with at least 2 vertices. Show that there exist 2 distinct vertices $s_{1}$ and $s_{2}$ such that the subgraphs $G \setminus \{s_{1}\}$ and $G \setminus \{s_{2}\}$ are both connected.
( $G \setminus \{s\}$ denotes the subgraph obtained from $G$ by removing the vertex $s$ together with all its incident edges)

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

Let $C = s_1 \text{--} \dots \text{--} s_k$ be a path of maximal length that never visits the same vertex twice.
Since $G$ is connected and has at least 2 vertices, we have $s_1 \neq s_k$ .
Let us show that $G \setminus \{s_1\}$ is connected, which by an analogous reasoning will imply that $G \setminus \{s_k\}$ is also connected.

Let $s$ and $t$ be vertices in $G \setminus \{s_1\}$ , and let $s \text{--} \dots \text{--} t$ be a path connecting them in $G$ .

If the path does not pass through $s_1$ , then it still exists in $G \setminus \{s_1\}$ .
If the path passes through $s_1$ , then each passage through $s_1$ is of the form $s_i \text{--} s_1 \text{--} s_j$ (with $i, j \neq 1$ ). Indeed, by maximality of $C$ , all neighbors of $s_1$ are in $C$ . The path can then be modified to avoid $s_1$ by following $C$ to go from $s_i$ to $s_j$ , which yields a path in $G \setminus \{s_1\}$ connecting $s$ and $t$ .

Report