Graphs for which the set of t-joins and t-cuts has ‘the max-flow-min-cut property’, i.e. for which the minimal defining system of the t-join polyhedron is totally dual integral, have been characterized by Seymour. An extension of this problem is to characterize the (uniquely existing) minimal totally dual integral defining system (Schrijver-system) of an arbitrary t-join polyhedron. This problem is solved in the present paper. The main idea is to use t-borders, a generalization of t-cuts, to obtain an integer minimax formula for the cardinality of a minimum t-join. (A t-border is the set of edges joining different classes of a partition of the vertex set into t-odd sets.) It turns out that the (uniquely existing) ‘strongest minimax theorem’ involves just this notion.
