Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Prove that every undirected connected graph with $|V| > 2$ has at least two vertices such that if one or both are removed (along with their incident edges) the resulting graph is still connected. Describe an efficient algorithm to find two such vertices.
How would I go about solving this?
Prove that every undirected connected graph with |V | > 2 has at least two vertices such that if one or both are removed (along with their incident edges) the resulting graph is still connected.
If your graph is connected, then you always have a Spanning Tree, now you can reduce the problem to proving that Every Finite Non-Trivial Tree has at Least 2 Leaf Nodes.
Describe an efficient algorithm to find two such vertices.
A very obvious way would be just to find 2 leaf nodes of your Spanning Tree.
