On the cut polyhedron

The cut polyhedron cut(G) of an undirected graph G = (V, E) is the dominant of the convex hull of all of its nonempty edge cutsets. After examining various compact extended formulations for cut(G), we study some of its polyhedral properties. In particular, we characterize all of the facets induced by inequalities with right-hand side at most 2. These include all of the rank facets of the polyhedron.