EDGE CONNECTIVITY OF SIMPLICIAL POLYTOPES

NEW

Problem: Reconstructed statement: For every $d\ge 3$, if $P$ is either a flag simplicial $d$-polytope or a balanced simplicial $d$-polytope, then every minimum edge cut in the graph $G(P)$ is trivial, i.e. consists of all edges incident with a single vertex.
This is the natural reading of Problem 3 in Pineda-Villavicencio–Ugon.

Result: The statement is false. A balanced $4$-polytope gives a counterexample.

Let $H=C_{10}*C_{10}$, the graph join of two 10-cycles. This is the graph of the simplicial $4$-polytope whose boundary complex is the join of two decagons; it is balanced by alternating two colors on each cycle. Every vertex of $H$ has degree $12$, and $\lambda(H)=12$: for a cut $X$, writing $a=|X\cap A|$, $b=|X\cap B|$, its size is

where $p_A,p_B$ are the cycle-boundary contributions; a direct case check gives at least $12$, with equality at a single vertex.

Let $O_4$ be the $4$-cross-polytope, with opposite facets

where $u_i$ and $v_i$ are nonadjacent antipodes. Glue two copies of the balanced polytope $H$ to $O_4$ by connected sums along $F^+$ and $F^-$, matching the four colors. The resulting simplicial $4$-polytope $P$ is balanced.

In $G(P)$, the two glued copies of $H$ are connected only through the cross-polytope edges between $F^+$ and $F^-$. There are exactly

such edges, since only the antipodal pairs $u_i v_i$ are missing. Removing these 12 edges disconnects $G(P)$, and the cut is not the star of a single vertex.

It remains to see it is minimum. If an edge cut of $G(P)$ had size $<12$, then its restriction to either copy of $H$ could not split that copy, since $\lambda(H)=12$. Hence each copy of $H$ would have to lie entirely on one side of the cut. If both lie on the same side, the cut is empty; if they lie on opposite sides, the cut is exactly the 12 cross-polytope edges above. Thus no smaller cut exists.

So $G(P)$ has a nontrivial minimum edge cut. Therefore the proposed statement is false for balanced $4$-polytopes.

Citation: No known prior citation for this exact counterexample. It uses the standard connected-sum construction for simplicial polytopes.