Describing edges in triangle-free 3-polytopes

Abstract

An edge e in a 3-polytope is of type ( k 1 , k 2 , k 3 , k 4 ) if the set of degrees of the vertices and faces incident with e is majorized by the vector ( k 1 , k 2 , k 3 , k 4 ) . 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 ( k 1 , k 2 ) × ( k 3 , k 4 ) if the set of degrees of its incident vertices is majorized by the vector ( k 1 , k 2 ) , while that of its incident faces, by ( k 3 , k 4 ) . The purpose of our paper is to prove the following description of edges in triangle-free 3-polytopes, 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.

The authors' abstract, as published at the source. Discrete Mathematics, 2026 · DOI ↗