2
$\begingroup$

How do I go about proving 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, and describe an efficient algorithm to find two such vertices.

$\endgroup$

marked as duplicate by Gilles Nov 30 '16 at 19:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from math.stackexchange.com Nov 30 '16 at 19:29

This question came from our site for people studying math at any level and professionals in related fields.

4
$\begingroup$

Hint: Find the connected graph's spanning tree (using an algorithm like breadth-first search). Consider the endpoints of a longest path in this spanning tree.

$\endgroup$
  • 3
    $\begingroup$ Why the longest path? Any leaves of a spanning tree will do. $\endgroup$ – Robert Israel Nov 21 '16 at 3:19
  • $\begingroup$ @RobertIsrael That's true. Typically, the way to prove that trees have leaves is by considering a longest path. $\endgroup$ – Adriano Nov 21 '16 at 4:04

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