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

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

 (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.

• V 1 = {r}, V 2 = V \ r. Then (1) becomes  (2)

• V 1 = {s}, V 2 = V \ s. Then (1) becomes  (3)

• V 1 = {r,s}, V 2 = V \{r,s}. Then (1) becomes  (4)

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

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

 (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:

• Let πT x π 0 denote the given inequality, and we want to prove this defines a facet of conv(S). Assume there exists S satisfying πT < π 0, so the face defined by the inequality is not equal to S.
• We need to show there is no other inequality gT x h satisfying all of the following:
1.
gT x h for all x S, so the constraint is valid.
2.
gT x = h for all x S satisfying πT x = π 0 (so it includes the same face).
3.
There is a point S with gT = h, πT < π 0 (so the face defined by gT x = h strictly contains the face implied by the original inequality).
4.
There is a point S with gT < h (so the face defined by gT x = h is not the whole of S).
• When S is full-dimensional, one way to show there is no other inequality satisfying all four conditions is to assume we have an inequality that satisfies the first two conditions and then show this inequality must just be a positive rescaling of πT x π 0.

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

 (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

• Let l V \{k} and set V 1 = V \{l}, V 2 = {l}. We have  (7)

• Consider edges where neither endpoint is in {i,j,k}. In particular, let l,m ⁄∈{i,j,k} with (l,m) E and take V 1 = V \{l,m}, V 2 = {l,m}. We have  (8)

It follows from (7) that

 (9)

• Now look at edges (j,l) where l ⁄∈{i,j,k}. Take V 1 = V \{j,l}, V 2 = {j,l}. We have  (10)

It follows from (7) that

 (11)

• In an analogous manner, we obtain  (12)

for l ⁄∈{i,j,k}.

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

• Next, we show that gij, gik, gjk have the same relationship as in (6). Take V 1 = V \{i}, V 2 = {i}. We obtain  (13)

Similarly, taking V 1 = V \ j, V 2 = j and using (11), we obtain

 (14)

From (13) and (14), we have

 (15)

agreeing with the relationship between these coefficients in (6).

• Finally, look at gkl for l ⁄∈{i,j,k}. Set V 1 = {i,k}, V 2 = V \{i,k}. We have
Now with V 1 = {i,k,l} and V 2 = V \{i,k,l}, we get
and thus from (15)

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