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