3
$\begingroup$

This is a problem from Algorithms by Dasgupta, Papadimitriou, and Vazirani (problem 3.27):

Two paths in a graph are called edge-disjoint if they have no edges in common. Show that in any undirected graph, it is possible to pair up the vertices of odd degree and find paths between each such pair so that all these paths are edge-disjoint.

Maybe I'm interpreting the question wrong, but isn't this a valid counterexample?

counterexample

All vertices have an odd degree (1 or 3), but the paths between all pairs are not disjoint..

$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

Seems like you are interpreting the question wrong.

You can pair the bottom two vertices (which leaves the middle and top for the other pair).

One path is the edge joining the top to middle and the other path is the path between the two bottom vertices, going through the middle vertex.

Note that that paths are edge disjoint, even though they share a vertex.

$\endgroup$

You must log in to answer this question.

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