Quoting Shai's answer (if i got you right) - we are checking that there is a min. cut that contains e1 but not e2. (other way is analogic)
algorithm
1. find f* - maximum flow in the normal graph
2. reduce e1 capacity by small constant* c (call this graph G') , run dinic again - if |f| did not reduce then answer is "no".
3. on the same graph G', increase e2 capacity by small constant d, run dinic again - if |f| did increase- then answer is "no"
finally return "yes"
correctness:
2 : if decreased <=> e1 exists on some min.cut .
3 :
because of the small constant then actually all min. cuts include e1.
then, if all cuts also include e2, then the flow will increase.
if it doesn't, then some cut contains e1 but not e2 .
- the small constant needs to be less than the minimum delta between any two edges. (can find it as part of the algorithm)