1
$\begingroup$

I'm trying to prove that a connected simple graph that has exactly 2 cut-vertices has a cut edge. My attempts at proving this are to somehow show that the two cut vertices are adjacent, which would mean that the edge that they share is the cut edge.

Any help would be appreciated!!

$\endgroup$
3
$\begingroup$

What you want to prove is not true. Here is a counterexample:

  O   O   O
 / \ / \ / \
O---O---O---O

In this case the two cut vertices happen to be adjacent, but the edge between them is not a cut edge. They don't need to be adjacent, though:

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