In this note, precise upper bounds are determined for the minimal degree-sum w of the vertices of a face in several classes of triangulated 3-polytopes in terms of the maximal length of a path consisting of 4-vertices. In particular, if no two 4-vertices are adjacent, then w~<37, and if no 4-vertex is adjacent to a 3-or 4-vertex, then w~<29. @ 1998 Elsevier Science B.V. All rights reserved
The weight of a face in a 3-polytope P is the degree-sum of its incident vertices. By w(P), or w, we denote the minimal weight of a face in P. If in P there are no vertices of degree 3 or 4, then as conjectured by Kotzig [3] and proved in [1], w~< 17, the bound being precise. In the presence of 4-vertices, w may be arbitrarily large, as shown by the double n-pyramid. For triangulated 3-polytopes without 4-vertices, Kotzig [4] announced w~<39. For arbitrary 3-polytopes, however, the absence of 4-vertices does not guarantee that w is bounded, as follows from the n-pyramid. Hereafter, we consider only triangulated 3-polytopes T, i.e., plane triangulations without loops and multiple edges. As proved in [2], confirming Kotzig's conjecture [4], if in T there is no 4-vertex, then w ~<29, and the bound is sharp. (The twice-capped icosahedron has w=3 +6+20=29.)
In this note we establish that, informally speaking, each triangulated 3-polytope has either a face of low weight or a long path consisting of 4-vertices. More specifically, we consider several classes of triangulated 3-polytopes in which w turns out to be restricted and find precise upper bounds for w in terms of the maximal length of a path consisting of 4-vertices. By an i,j-edge we mean an edge joining a vertex of degree i with that of degree j. Our main result is: