[Math] Disjoint paths in a directed graph

graph theory

Suppose you have a directed graph $G=(V,E)$. For all $v\in V$ the number of edges going into $V$ is equal to the number of edges out of $V$. Assume that vertices cannot have edges pointing to themselves.

Suppose there are $k$ mutually disjoint paths from a node $v_1$ to a node $v_2$. Does it follow that there are $k$ mutually disjoint paths from $v_2$ to $v_1$?

I have a feeling this is false but have not been able to come up with any counterexamples.

Best Answer

If by "disjoint" you mean "vertex-disjoint", this is false, e.g.:

            +------
            |     |
            |     V
 v1 -> a -> v2 -> c -> v1
 |          ^     |    ^
 |          |     |    |
 +---> b ---+     +----+

(where $v_1$ appears twice for graphical convenience but is the same vertex).

If by "disjoint" you mean "edge-disjoint", this is true. Remove the edges of the $k$ mutually edge-disjoint paths from $v_1$ to $v_2$. Now all vertices still have equal in-degree and out-degree, except $v_1$ has $k$ more edges leading in and $v_2$ has $k$ more edges leading out. Start a path from $v_2$ by taking any of the edges. Whatever vertex you reach via an edge leading to it must have a matching edge leading away from it. Keep following these edges. Eventually you must end up at $v_1$, since there's no other vertex with more edges leading in than out. This completes the first path. Remove its edges and repeat $k-1$ times.

Related Question