A connection between a paths in a flow network

20 Views Asked by At

Let $G=(V,E)$ be a flow network with source $s$ and sink $t$.

The capacities of all the edges are positive integers.

An edge $e=(a,b)$ will be called successful if, for each maximum flow $f$, there exists in the residual network corresponding to $f$, both a path from the source $s$ to $a$ and a path from $b$ to the sink $t$.

An edge $e=(a,b)$ will be called special if in every minimum cut holds that $a∈S$ where $s∈S$ and $b∈T$ where $t∈T$.

The question asks to prove that if $e=(a,b)$ is special then it's also successful.

Here is what I wrote:

From the fact that $e=(a,b)$ is special, at the end of Ford–Fulkerson method, we can derive that there exists a path from $s$ to $a$ in the corresponding residual network.

I will show now that there exists a path from $b$ to $t$.

Let $F$ be the residual network at the end of Ford–Fulkerson method.

Let us look at $F^{Rev}$.

$F^{Rev}$ representing a residual network corresponding to the original network but the directions of the edges are reversed, and the source is $t$ and the sink is $s$.

However, from the fact that $e=(a,b)$ is special, there exist a path from $t$ to $b$ in $F^{Rev}$ , and thus, there exist a path from $b$ to $t$ in $F$.

Therefore $e=(a,b)$ is successful $∎$

I want to know if this is a correct proof.