We present an explicit closed-form formula for the vertices of the classical cut polytope $\operatorname{ CUT}(n)$, defined as the convex hull of cut vectors of the complete graph $K_n$. Our derivation proceeds via a related polytope, denoted $\mathbf{ 1}$-$\operatorname{ CUT}(n)$, whose vertices are obtained by flipping all bits of the $\operatorname{ CUT}(n)$ vertices. This polytope arises naturally in a probabilistic context involving agreement probabilities among symmetric Bernoulli random variables which serves as the starting point of this work. Our approach constructs the vertex set recursively via a binary encoding that stems from this probabilistic perspective. We prove that the resulting sequence of encoded integers, when appropriately scaled, exhibits an almost-linear behavior closely approximating the line $y = x - \frac{ 1}{ 2}$. This structure motivates the introduction of the alternating cycle function, an integer-valued map whose key property is power-of-two composition invariance. The function serves as the foundation for our closed-form enumeration formula. The result provides a rare instance of explicit vertex characterization for a $0$/$1$-polytope and offers a transparent combinatorial construction independent of enumeration algorithms.
Categories: math.CO cs.DM math.OC math.PR