On Odd Cuts and Plane Multicommodity Flows
Paul D. Seymour · Proceedings of the London Mathematical Society · 1981
Let T be an even subset of the vertices of a graph G. A T-cut is an edge-cutset of the graph which divides T into two odd sets. We prove that if G is bipartite, then the maximum number of disjoint T-cuts is equal to the minimum cardinality of a set of edges which meets every T-cut. (A weaker form of this was proved by Edmonds and Johnson.) We deduce a solution to the real-valued multi-commodity flow problem for a class of planar graphs; and we also solve the integral 2-commodity flow problem for the same class of graphs, by a further analysis of the T-cut problem when|T| = 4.