1
$\begingroup$

The question:

Show that every graph with 3 or more vertices will have a separation edge on the condition that it also has a separation vertex.


I know that a graph of 3 vertices in the shape of a line has 2 separating edges and 1 separation vertex. So it's true for the smallest case.

A separation edge is in multiple biconnected components. But I'm not sure how to link equivalence classes to show that it's true in the general case. Is it enough to say that since a separation vertex belongs to multiple equivalence classes, then it must have a separation edge?

$\endgroup$
2
$\begingroup$

No. The implication that existence of a cut vertex implies existence of a cut edge is false.

Consider the example of the butterfly graph:

Butterfly Graph Drawing

Then the center vertex is a cut vertex while there are no cut edges present in the graph.

$\endgroup$
2
  • $\begingroup$ Does that mean that a separation/cut edge doesn't imply a separation vertex either? $\endgroup$ – nodel Nov 22 '17 at 13:43
  • 1
    $\begingroup$ Nope that is still true, if you have a separation edge then removing it disconnects the graph. If you then remove any of the endpoints on that edge then that edge is also removed, hence those two vertices becomes the separation vertices. $\endgroup$ – Peeyush Kushwaha Nov 22 '17 at 13:44

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.