On the cut polytope

The cut polytopeP _C (G) of a graphG=(V, E) is the convex hull of the incidence vectors of all edge sets of cuts ofG. We show some classes of facet-defining inequalities ofP _C (G). We describe three methods with which new facet-defining inequalities ofP _C (G) can be constructed from known ones. In particular, we show that inequalities associated with chordless cycles define facets of this polytope; moreover, for these inequalities a polynomial algorithm to solve the separation problem is presented. We characterize the facet defining inequalities ofP _C (G) ifG is not contractible toK ₅. We give a simple characterization of adjacency inP _C (G) and prove that for complete graphs this polytope has diameter one and thatP _C (G) has the Hirsch property. A relationship betweenP _C (G) and the convex hull of incidence vectors of balancing edge sets of a signed graph is studied.