# Prove connected graph minus one vertex still connected.

Let G be a connected graph with at least two vertices. Prove that G has a vertex v such that if v is removed from G (along with all edges incident with it), the resulting graph is also connected.

Hint: Consider a spanning tree and one of its leaves.

So I know that (using the hint), if the graph is a tree, one of such vertices that has this feature would obviously be a leaf vertex. The problem is, this problem doesn't specifically state to prove this for Trees, but for graphs in general. Any help here as to where to start would be appreciated.

• The hint manifestly gives you the solution. – Crostul Nov 30 '15 at 20:57
• If a subgraph is connected, then the graph itself is connected. – Michael Burr Nov 30 '15 at 21:06
• No. Do you know that a graph $G$ is connected if and only if it has a spanning tree $T$? Then, if you remove a leave of the spanning tree, what it remains is a tree (say $T'$) spanning the resulting graph (say $G'$). – Crostul Nov 30 '15 at 21:06
• @MichaelBurr you mean if a subgraph on all vertices of a graph is connected... – Ben Grossmann Nov 30 '15 at 21:11
• Possible duplicate of Proof that any simple connected graph has at least 2 non-cut vertices. – Hendrix Sep 26 '19 at 13:40

Since $G$ is connected, it has a spanning tree. You can delete any leaf $v$ from the spanning tree and the graph still has a spanning tree, so is still connected.
Without using the hint: Choose a vertex $u,$ and then choose a vertex $v$ at maximum distance from $u.$ To see that $G-v$ is connected, consider any other vertex $w.$ Since $G$ is connected, there is a path from $u$ to $w$ in $G;$ the shortest such path does not pass through $v,$ so it is a path in $G-v.$ (Of course this is more or less the way you would prove that a tree has a leaf.)