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$

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .