The cut polytope \(P_ C(G)\) of a graph \(G=(V,E)\) is the convex hull of the incidence vectors of all edge sets of cuts of G. We show some classes of facet-defining inequalities of \(P_ C(G)\). We describe three methods with which new facet-defining inequalities of \(P_ 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 of \(P_ C(G)\) if G is not contractible to \(K_ 5\). We give a simple characterization of adjacency in \(P_ C(G)\) and prove that for complete graphs this polytope has diameter one and that \(P_ C(G)\) has the Hirsch property. A relationship between \(P_ C(G)\) and the convex hull of incidence vectors of balancing edge sets of a signed graph is studied.

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.