1
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ The hint manifestly gives you the solution. $\endgroup$ – Crostul Nov 30 '15 at 20:57
  • 3
    $\begingroup$ If a subgraph is connected, then the graph itself is connected. $\endgroup$ – Michael Burr Nov 30 '15 at 21:06
  • 3
    $\begingroup$ 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'$). $\endgroup$ – Crostul Nov 30 '15 at 21:06
  • 2
    $\begingroup$ @MichaelBurr you mean if a subgraph on all vertices of a graph is connected... $\endgroup$ – Ben Grossmann Nov 30 '15 at 21:11
  • 5
    $\begingroup$ Possible duplicate of Proof that any simple connected graph has at least 2 non-cut vertices. $\endgroup$ – Hendrix Sep 26 '19 at 13:40
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.