For any flow network N, add an edge $e_{ts}$ and color it black. Color all other edges in N with black, red or green, then at least one of the following two cases is true:

1) There exists a cycle C which includes $e_{ts}$ and is composed only with black and red edges, in which all black edges points to the same direction(all clockwise/anticlockwise in the cycle)

2) There exists a edge set A which includes $e_{ts}$ and is composed only with black and green edges, where the vertices in G-A can be divided into two sets $V_1$ and $V_2$ (suppose t is in $V_1$), such that all black edges point from $V_1$ to $V_2$

I guess I may need to construct a feasible flow from s to t and $e_{ts}$ joins the sink and the source. But I'm not sure how to do that.

  • $\begingroup$ What is "form a bipartite" supposed to mean? And is G-A the complement of A in G? If A consists of all the black edges in G, then the graph of black edges in G-A is trivially bipartite. $\endgroup$ – Angela Richardson May 21 '13 at 10:19
  • $\begingroup$ @AngelaRichardson my bad, I restated the problem wrongly. And G-A is the complement of A in G. And there has to be a black edge in G-A $\endgroup$ – arax May 21 '13 at 10:57
  • $\begingroup$ So $e_{ts}$ is not allowed to be the only black edge. Picking all but one of the black edges for $A$ would always leave $G-A$ as a one-edge, bipartite graph. $\endgroup$ – Angela Richardson May 21 '13 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.