We want to find whether there is some cut that contains $e_1$ but not $e_2$.

1. Find the max flow f.

2. Decrease the capacity of $e_1$ to 0. Call this new network G'.

3. Find the max flow in G', f'. We saw in the homework that some cut contains $e_1$ iff f-f'=c(e). If this is not the case, return false.

4. Increase the capacity of $e_2$ in G'. Call this new network G''.

5. Find the max flow in G'', f''. We saw in the homework that every cut of G'contains $e_2$ iff f''>f'. If this is the case, return false.

6. Return true.

We want to show that we return true iff there is a cut with $e_1$ but not $e_2$:

We use the following lemma:

Lemma 1: C = (S,T) is a min cut of G' iff C is a min cut of G such that $e_1$ crosses C (i.e. $e_1=(u,v), u \in S, v \in T$).

Proof: => C's capacity in G' is f'. If it doesn't hold that $u \in S, v \in T$, then the value of the min cut of G would be f'. Therefore $u \in S, v \in T$, hence the capacity of C in G is f.

<= as C is a min cut in G, its capacity is f, and as $u \in S, v \in T$, its capacity of C in G' is exactly f'=f-c(e).

From this, we can see that:

Lemma 2: $e_2$ is in every min cut of G' iff every cut in G that contains $e_1$ must contain $e_2$.

Proof: => From => of Lemma 1.

<= From <= of Lemma 1.