# Why network flow satisfy the transitive property?

Suppose $$G=(V,E)$$ be a directed graph , and let $$u,v,w$$ be distinct vertices. Suppose there are $$k$$ edge disjoint paths from $$u$$ to $$v$$ in $$G$$, and $$k$$ edge disjoint paths from $$v$$ to $$w$$ in $$G$$. The paths from $$u$$ to $$v$$ van share edges with the paths from $$v$$ to $$w$$. Then, how to show that there are $$k$$ edge disjoint paths from $$u$$ to $$w$$ in $$G$$ using Menger's theorem or MaxFlow-MinCut.

Update: I have already proved the following statement: Given an integer $$k>0$$, $$G$$ has $$k$$ edge disjoint paths from $$s$$ to $$t$$ if and only if there is an $$s,t$$ flow of value $$k$$ in $$G$$.

By the above statement, we know that $$G$$ has a $$u,v$$ flow of value k, and $$G$$ has a $$v,w$$ flow of value k, but how can we show there is a $$u,w$$ flow of value $$k$$ in $$G$$? This means I have to prove the transitivity of a flow, my thought is to use the flow conservation property of internal vertex to prove that, the internal vertex which joins the $$u,v$$ flow and $$v,w$$ flow is $$v$$. Is this the right approach or there is a better way to approach this?

An $$x,y$$-flow of value $$k$$ is a flow with excess $$-k$$ at $$x$$ ($$k$$ more flow leaving than entering), excess $$+k$$ at $$y$$ ($$k$$ more flow entering than leaving) and excess $$0$$ at every other node (flow conservation).

So if you add together a $$u,v$$-flow of value $$k$$ and a $$v,w$$-flow of value $$k$$ (edge by edge), you get something that's almost like a $$u,w$$-flow of value $$k$$. The only problem is that some edges might be used twice in the sum, exceeding capacity.

Prove that if an edge $$xy$$ is used twice in the sum of the two flows, then the sum of the flows also contains a cycle containing $$xy$$. Then, we can subtract $$1$$ from the flow along each edge of the cycle, and avoid this problem. Repeat for every such edge, and you'll get an actual $$u,w$$-flow of value $$k$$.

• I have drawn a picture of an instance where an edge $xy$ is used twice in the sum of two flows, it indeed must contain a cycle containing $xy$. But can you explain more about why we have to subtract 1 from the flow along each edge of the cycle? How can subtract 1 helps? Which problem it avoids specifically? Thanks. Commented Mar 29, 2021 at 16:51
• let's say I have a $u,v$ flow of value $2$, where the flow is a simple path $(u,a,b,c,v)$, and I have a $v,w$ flow of value $2$, where the flow is simple path $(v,z,b,c,w)$. Then we have a common edge $bc$ being used twice, so $bc$ has carries flow of value $4$, but after subtracting $1$ from the cycle, the edge $bc$ still carries flow of value $3$, which means it is still used twice? So my question is why we should subtract $1$ or am I interpreting something wrong? Commented Mar 29, 2021 at 17:09
• Your initial $u,v$-flow and $v,w$-flow should assign value at most $1$ to each edge, if they correspond to sets of edge-disjoint paths. Commented Mar 29, 2021 at 18:32

I would probably use Menger's Theorem. If there were a small $$u$$-$$w$$ cut, then $$v$$ is "on one side or the other" of the cut. But that seems like a problem.