An improvement of Lebesgue’s description of edges in 3-polytopes and faces in plane quadrangulations

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 ) . This also provides a description of the faces of quadrangulated 3-polytopes in terms of degrees of their incident vertices. The purpose of our paper is to prove that every 3-polytope has an edge of one of the types ( 3 , 3 , 3 , ∞ ) , ( 3 , 3 , 4 , 9 ) , ( 3 , 3 , 5 , 6 ) , ( 3 , 4 , 4 , 5 ) , where all parameters except possibly 9 are best possible. We believe that 9 here is sharp and thus the whole description is tight. Our proof relies on the discharging method.