I have been trying to prove this for a decent amount of time, but nothing is coming to my mind. Anybody have some tips? I'd be happy to see an explanation.

I also found this question on StackOverflow, that says this:

If the direct u->v traffic doesn't knock out any links in v->u, then the v->u problem is equivalent of finding the maximum flow from v->u as if the u->v flow doesn't happen.

He describes how it can be solved, but still there is no answer to the question that the author asked.

So, the problem is:

Given a directed graph, at each vertex the number of incoming and outgoing edges is the same. Let there be k edge-disjoint paths from b to a in this graph.

How can I prove that it also contains k edge-disjoint paths from a to b?

Thanks in advance!

CodePudding user response：

We can try to argue about the general case where the graph is a multi-graph (i.e. can have multi-edges and loops).

Note: Following the convention that two copies of an edge count towards in and degree twice. And a loop count towards both in and out degree once. Also assuming when you say paths, you mean simple paths.

Using induction on the number of vertices in the graph G.

Base case: G has only vertices a and b.

Now as there are k edge-disjoint paths from a to b, all of them are simply k copies of the edge a->b. Thus to have in and out degrees same for both vertices there have to be k copies of b->a, and thus the claim holds.

Induction G has n >=1 vertices apart from a and b.

Let the nth vertex be u. Let in-degree of u, same as its out-degree be d. Let the d vertices with edges "going into" u be s1,s2,..,sd and similarly the d vertices with edges going out from u be t1,t2,..,td (note all these vertices may not be unique). Just pair these vertices up. Say si with ti (1<=i<=d). Now just "short-circuit" the vertex u, i.e. rather than having the edge si->u->ti, just have si->ti. Let the new graph be G'. It is trivial to see in and out degree of vertices are still the same in G' (as it was in G). And it is not hard to argue that the new graph still has k disjoint paths from a to b. Additionally G' has one less vertex. So apply inductive hypothesis, and claim holds for G'. Lastly not hard to check again, un-short circuiting u still keeps the claim intact for G.