Proofs for the MaxCut Polyhedron
John Mitchell

1 Dimension

Given a graph G = (V,E), a cut partitions V into two sets V 1 and V 2. An edge e = (u,v) is in the cut if exactly one of its endpoints is in V 1. We represent this cut using the binary vector x n, where n = |E|, with

      {
xe =     1  if e is in the cut
         0  otherwise.

Let S n denote the set of incidence vectors of feasible solutions and let conv(S) denote its convex hull.

The proofs below are adapted from Deza and Laurent (Mathematical Programming 56:121–160, 1992).

Theorem 1 The MaxCut polyhedron conv(S) is full-dimensional.

Proof. If the polyhedron is not full-dimensional then there exists a nontrivial constraint

∑  a x  =  b
     e e
e∈E
(1)

that is satisfied by all x S. We show that any such equality must actually be trivial with b = 0 and ae = 0 for all e E.

b = 0 : One valid partition is to take V 1 = V and V 2 = , which results in xe = 0 for all e E. Hence the left hand side of (1) evaluates to zero, so we must have b = 0.

ae = 0e E : Pick an arbitrary edge e = (r,s) and show ae = 0 by considering three cuts.

Then (2)+(3)-(4) implies

2a   = 0   ⇒    a  = 0.
  rs             Że

This holds for all e E, as required.

2 Facets

Let C E denote a cycle in the graph. Let F C with |F| odd. We have the valid constraint

∑         ∑
    xe -      xe ≤  |F | - 1.
e∈F      e∈C\F
(5)

This is facet-defining provided the cycle contains no chords; that is, there are no edges of the form (u,v) E where u and v are nonconsecutive nodes in the cycle.

One way to prove a valid constraint is facet-defining is to show that it is not implied by another valid constraint. This lets us state the general proof-by-contradiction procedure as follows:

We show that one particular odd-subset constraint is facet defining. The proof can be extended to show that any inequality of the form (5) is facet defining for |F| odd and C chordless.

In particular, consider the inequality

xij - xik - xjk ≤ 0
(6)

for three vertices i,j,k V and three edges (i,j), (i,k), (j,k) E. This constraint is satisfied at equality by three types of cuts:

1.
{i,j,k}⊆ V 1.
2.
{i,k}⊆ V 1, j V 2.
3.
{j,k}⊆ V 1, i V 2.

The remaining vertices can be placed in either V 1 or V 2. The roles of V 1 and V 2 can be reversed.

Assume inequality (6) is implied by gT x h, and look at possible choices for g and h.

First, determine h. The cut V 1 = V , V 2 = satisfies (6) at equality, so it must also satisfy gT x = h from the second requirement in the general procedure on the previous page. For this cut, x = 0, so we must have h = 0, the same right hand side as in (6). So gT x = 0 for any x S that satisfies (6) at equality.

Now determine the values of g by looking at various cuts. In this way, we can set up multiple equalities that must be satisfied by the components of g, and then these can be combined to show g is a multiple of the original coefficients in (6). In particular, we want to show that

g  = g   = - g  , and
 ik     jk      ij
grs = 0  if {r,s} ⁄⊆ {i,j,k}.

We still need to determine gij, gik, and gjk, and also gkl for l ⁄∈{i,j}.

So all coefficients are positive multiples of those in (6).