On Cut Polytopes and Graph Minors

NEW

Problem: For finite simple graphs, let

$$\operatorname{CUT}(G)=\operatorname{conv}\{\chi^{\delta(S)}:S\subseteq V(G)\}.$$

Let $P_5(G)$ be the projection to $E(G)$ of the complete-graph relaxation in which every restriction to at most five vertices lies in the corresponding complete-graph cut polytope. A graph is $K_5$-friendly if

$$P_5(G)=\operatorname{CUT}(G).$$

Here $C_7^2$ is the square of the 7-cycle, and $DW_5=K_2+C_5$. The conjecture is:

$$G\text{ is }K_5\text{-friendly} \iff G\text{ has no }K_6,\ C_7^2,\ DW_5\text{ minor}.$$

Result: The conjecture is true.

Use the known facts from Kaparis–Letchford–Mourtos and Barahona–Mahjoub that $K_5$-friendliness is minor-closed, is preserved under separations of order at most $3$, $K_6,C_7^2,DW_5$ are not $K_5$-friendly, and $K_6-e$ is $K_5$-friendly.

It remains only to prove the missing 4-vertex-cover case.

Lemma. Every graph with a vertex cover of size at most $4$ is $K_5$-friendly.

Proof. By minor-closedness it suffices to consider

$$M_m=K_4+\overline{K_m},$$

with cover $U$, $|U|=4$, and independent set $W$. Take $x\in P_5(M_m)$, with a complete-graph $P_5$-lift.

Let $D$ be the set of probability distributions on the eight cuts of $K_U$ whose expected edge-vector is $x|_{E(K_U)}$. Since $\operatorname{CUT}(K_4)$ has dimension $6$ and eight vertices, $D$ is a possibly degenerate interval.

For each $w\in W$, let $D_w\subseteq D$ be the boundary distributions on $U$ extendable to a cut distribution on $U\cup\{w\}$ realizing $x$. Since $U\cup\{w\}\cong K_5$, each $D_w$ is a nonempty interval.

For distinct $w,w'$, restrict the chosen lift to $U\cup\{w,w'\}$ and delete the edge $ww'$. This gives a point of $P_5(K_6-e)$, hence of $\operatorname{CUT}(K_6-e)$. Its boundary law on $U$ lies in $D_w\cap D_{w'}$. Thus the intervals $D_w$ pairwise intersect, so by Helly’s theorem for intervals,

$$\bigcap_{w\in W}D_w\neq\varnothing.$$

Choose $\rho$ in this intersection. For each $w$, choose an extension distribution with boundary law $\rho$. Sampling a cut of $U$ according to $\rho$, then conditionally independently sampling each $w$’s side using its chosen extension, gives a cut distribution on $M_m$ with expectation $x$. Hence $x\in\operatorname{CUT}(M_m)$. ∎

Now let $G$ be obstruction-free and minor-minimal non-$K_5$-friendly. The separation theorem forces $G$ to be 4-connected. By Ding–Lewchalermvongs–Maharry’s structure theorem, every 4-connected $C_7^2$-minor-free graph is planar, a double wheel, has a vertex cover of size at most $4$, is $K_6$, is $L(K_{3,3})$, or is one of finitely many graphs $\Gamma_1,\dots,\Gamma_5$.

Each case is friendly or excluded: planar graphs are $K_5$-minor-free; $K_6$ is forbidden; $DW_n$ with $n\ge5$ contains $DW_5$ as a minor, while $DW_3,DW_4$ are subgraphs of $K_6-e$; the 4-vertex-cover case is the lemma; and $L(K_{3,3}),\Gamma_1,\dots,\Gamma_5$ are verified friendly by Kaparis–Letchford–Mourtos. Contradiction.

Thus exactly the graphs with no $K_6,C_7^2,DW_5$ minor are $K_5$-friendly.

Citation: No prior resolving citation known. Ingredients used: Kaparis, Letchford, Mourtos, “On cut polytopes and graph minors,” Discrete Optimization 50 (2023), 100807; Barahona–Mahjoub, “On the cut polytope,” Mathematical Programming 36 (1986), 157–173; Ding–Lewchalermvongs–Maharry, “Graphs with no $\overline{P_7}$-minor,” Electronic Journal of Combinatorics 23 (2016), P3.9.