Graph Theory about connectivity

Question

Given any connected and undirected graph G(V,E), show, that there always exists a vertex v in G whose removal from the graph does not affect the connectivity of G, that is, there exists a path between each pair of vertices. Show a O(|E|+|V|) time algorithm to find such a vertex.

So I started off trying to think of an algorithm that would solve this problem. I figured a good way to go is using a breadth-first-search (BFS). Then you would be able to remove vertex in the highest level layer. Since BFS is done by layers, removing a vertex from the highest layer shouldn't disconnect the other vertices from the graph.

Am I on the right track? And how would I prove this?

Answer 1

Regarding the algorithm, you could run a DFS or BFS and find the first vertex with no children. If such node does not exist, then you must have a cycle, and then you could return any node.

Regarding the proof. Perhaps by induction? You could prove that if you add a vertex with a single edge (a leaf vertex) to any connected, undirected graph, you could always remove it, without affecting the connectivity.

Answer 2

Let G be a connected, undirected Graph.

Because G is connected, consider a spanning tree M of G. This spanning tree M has at least one vertex which has degree 1 (leaf-vertex). So by removing such a particular vertex from G we still have a connected graph, that is, there exists a path between each pair of vertices.