A POLYHEDRON WITH ALL S-T CUTS AS VERTICES, AND ADJACENCY OF CUTS

Consider the polyhedron represented by the dual of the LP formulation of the maximum s-t flow problem. It is well known that the vertices of this polyhedron are integral, and can be viewed as s-t cuts in the gi ven graph, In this paper we show that not all s-t cuts appear as verti ces, and we give a characterization. We also characterize pairs of cut s that form edges of this polyhedron. Finally, we show a set of inequa lities such that the corresponding polyhedron has as its vertices all s-t cuts.