2
$\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$
6
$\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$

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.