Edge connectivity of simplicial polytopes

Vincent Pilaud; Guillermo Pineda-Villavicencio; Julien Ugon

doi:10.1016/j.ejc.2023.103752

paper

Edge connectivity of simplicial polytopes

arXiv:2209.07792 · doi:10.1016/j.ejc.2023.103752

Abstract

We show that the graph of a simplicial polytope of dimension $d \geq 3$ has no nontrivial minimum edge cut with fewer than $d (d + 1) /2$ edges, hence the graph is $min {δ, d (d + 1) /2}$ -edge-connected where $δ$ denotes the minimum degree. When $d = 3$ , this implies that every minimum edge cut in a plane triangulation is trivial. When $d \geq 4$ , we construct a simplicial $d$ -polytope whose graph has a nontrivial minimum edge cut of cardinality $d (d + 1) /2$ , proving that the aforementioned result is best possible.

10 pages, 1 figure. This paper subsumes the results of arXiv:2111.07050. Version 2: Improvement of the main result and major revision of its proof due to a serious flaw in the previous version. Version 3: Minor corrections