THE INEQUICUT CONE

Given a complete graph K(n) on n nodes and a subset S of nodes, the cu t delta(S) defined by S is the set of edges of K(n) with exactly one e ndnode in S. A cut delta(S) is an equicut if absolute value of S = [n/ 2] or [n/2] and an inequicut, otherwise. The cut cone C(n) (or inequic ut cone IC(n)) is the cone generated by the incidence vectors of all c uts (or inequicuts) of K(n). The equicut polytope EP(n), studied by Co nforti et al. (1990), is the convex hull of the incidence vectors of a ll equicuts. We prove that IC(n) and EP(n) 'inherit' all facets of the cut cone C(n), namely, that every facet of the cut cone C(n) yields ( by zero-lifting) a facet of the inequicut cone IC(m) for n < [m/2] and of EP(m) for m odd, m greater-than-or-equal-to 2n + 1. We construct s everal new classes of facets, not arising from C(n), for the inequicut cone IC(n) and we describe its facial structure for n less-than-or-eq ual-to 7.