  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}(G)$ is a graph whose vertex set is the vertex set
of the polytope, and the edge set is the set of geometric edges or
one-dimensional faces of the polytope. We study the diameter and the clique
number of 1-skeleton of cut polytopes for several classes of graphs. These
characteristics are of interest since they estimate the computational
complexity of the max-cut problem for certain computational models and classes
of algorithms. It is established that while the diameter of the 1-skeleton of a
cut polytope does not exceed $|V|-1$ for any connected graph, the clique number
varies significantly depending on the class of graphs. For trees, cacti, and
almost trees (2), the clique number is linear in the dimension, whereas for
complete bipartite and $k$-partite graphs, it is superpolynomial.
