On Odd Cuts and Plane Multicommodity Flows

Let Τbe an even subset of the vertices of a graph G.A T-cut is an edge-cutset of the graph which divides Τinto two odd sets. We prove that if Gis 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.