2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. See also meta.cs.stackexchange.com/q/1284/755. $\endgroup$ – D.W. Nov 21 '16 at 17:31
5
$\begingroup$

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.

$\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.