I have the impression that if I take a simple, connected graph then I can (provided it has a vertex number greater than or equal to 2) remove a vertex and obtain a connected subgraph.
This doesn’t work with all vertices, there are some that I can’t remove.
For instance,
I can’t remove E without losing connectivity but I can remove A,B,C or D.
But there is always one that I can rule out. Do you have a way to prove this result?
>Solution :
Let G be any connected graph. Then G has at least one spanning tree. Let T be any spanning tree of G. Let v be any leaf of T. If we delete v, T \ {v} is connected, and is a subgraph of G \ {v} so G \ {v} is connected.
Well-known results this uses:
- Every connected graph has at least 1 spanning tree
- Deleting a leaf from an n-vertex tree results in an (n-1)-vertex tree