Let G=(V,E) be a graph and let w be a weight function w:E⇒Z’+. Let T⊆V be an even subset of the vertices of G. A T-cut is an edge-cutset of the graph which divides T into two odd sets. A T-join is a minimal subset of edges that meets every T-cut (a generalization of solutions to the Chinese Postman problem). The main theorem of this paper gives a tight upper bound on the difference between the minimum weight T-join and the maximum weight integral packing of T-cuts. This difference is called the (T-join) integral duality gap. Let τw be the minimum weight of a T-join, and let νw be the maximum weight of an integral packing of T-cuts. If F is a non-empty minimum weight T-join, and nF is the number of components of F, then it is proven that τw-νw•nF-1. This result unifies and generalizes Fulkerson’s result for ℝTℝ=2 and Seymour’s result for ℝTℝ=4. For a certain integral multicommodity flow problem in the plane, which was recently proved to be NP-complete, the above result gives a solution such that for every commodity the flow is less than the demand by at most one unit.
