On 1-skeleton of the cut polytopes

Andrei V. Nikolaev

Given an undirected graph $G=(V,E)$, the cut polytope $\mathrm{CUT}(G)$ is defined as the convex hull of the incidence vectors of all cuts in $G$. The 1-skeleton of $\mathrm{CUT}…