# Cut polytope

## Contents |

### Introduction

This article introduces the polytope of cuts in a graph. Understanding its geometry is not only interesting from a theoretical point of view, but also necessary in order to be able to design an effective branch-and-cut algorithm for the max-cut problem. The latter can be used for determining exact ground states of Ising spin glasses, cf. the article about the computation of exact ground states of Ising spin glasses.

### Definitions

The cut polytope is the convex hull of the incidence vectors of cuts in a graph. An explanation is given in the following.

Let δ(*W*) be the cut associated with node set *W* ⊆ *V* of a graph *G* = (*V*,*E*). With each cut, we can associate a so-called incidence vector of dimension | *E* | that contains an entry for each edge in *G*. In case edge *e* is in the cut, the corresponding entry is 1, otherwise it is 0. In formulas, let the incidence vector for a cut δ(*W*) be defined by

Let us associate with each of the 2^{|V|-1} many cuts in *G* their corresponding incidence vectors. The latter are 0-1 vectors living in | *E* | -dimensional space. Taking the convex hull of all incidence vectors of cuts in *G*, we get the cut polytope *P*_{C}(*G*):

- .

### Examples

#### Example (cut polytope for a graph consisting of a triangle)

The smallest interesting example for a cut polytope can be found for a graph that is a cycle of length three (a triangle), see Figure 1.

For the triangle, we have four different cuts. Let us order the coordinates as (*x*_{12},*x*_{23},*x*_{13}), where e.g., *x*_{ij} refers to the edge between node *i* *a**n**d* *j*.

The set of characteristic cut vectors for the triangle in Figure 1 is

- .

In Figure 2 we show the cut polytope for the graph of Figure 1 *P*_{C}(*K*_{3}).

Understanding the geometry of the cut polytope in higher dimensions is essential for the design of an effective branch-and-cut algorithm for max-cut.