Abstract: An edge e in a 3-polytope is of type (k1,k2,k3,k4) if the set of degrees of the vertices and faces incident with e is majorized by the vector (k1,k2,k3,k4). In 1940, Lebesgue proved that every 3-polytope has an edge of one of the types (3,3,3,∞),(3,3,4,11),(3,3,5,7), (3,4,4,5). Although Lebesgue’s description was improved for several restricted classes of 3-polytopes, beginning with Kotzig’s Theorem from 1955 saying that every 3-polytope has an edge with the degree-sum of its end-vertices at most 13, the first strengthening of Lebesgue’s Theorem was obtained only in 2019 by Borodin and Ivanova: in fact, “(3,3,3,∞),(3,3,4,9), (3,3,5,6),(3,4,4,5) holds”. An edge e in a 3-polytope is of type (k1,k2)×(k3,k4) if the set of degrees of its incident vertices is majorized by the vector (k1,k2), while that of its incident faces, by (k3,k4). The purpose of our paper is to prove the following description of edges in triangle-free 3polytopes, where all parameters are best possible: “(3,3) × (4,8),(3,3) × (5,6),(3,4) × (4,5),(3,5) × (4,4)”. Our principal difficulty was to find constructions confirming the sharpness of the first and third options, whereas those for the second and fourth ones are well-known.

Cite: Borodin O.V. , Ivanova A.O.
Describing edges in triangle-free 3-polytopes
Discrete Mathematics. 2026. V.350. N2. 115428 . DOI: 10.1016/j.disc.2026.115428 OpenAlex

Dates:

Submitted:	May 23, 2025
Accepted:	Sep 7, 2026

Identifiers:

≡ OpenAlex:

W7213284619

Altmetrics: