On a min–max theorem on bipartite graphs Original Research Article

Frank et al. (Math. Programming Stud. 22 (1984) 99–112) proved that for any connected bipartite graft (G,T), the minimum size of a T-join is equal to the maximum value of a partition of A, where A is one of the two colour classes of G. Their proof consists of constructing a partition of A of value |F|, by using a minimum T-join F. That proof depends heavily on the properties of distances in graphs with conservative weightings. We follow the dual approach, that is starting from a partition of A of maximum value k, we construct a T-join of size k. Our proof relies only on Tutteʹs theorem on perfect matchings. It is known (J. Combin. Theory Ser. B 61 (2) (1994) 263–271) that the results of Lovász on 2-packing of T-cuts, of Seymour on packing of T-cuts in bipartite graphs and in grafts that cannot be T-contracted onto (K4,V(K4)), and of Sebő on packing of T-borders are implied by this theorem of Frank et al. The main contribution of the present paper is that all of these results can be derived from Tutteʹs theorem.