Describing edges in normal plane maps having no adjacent 3-faces

Abstract

The weight $w(e)$ of an edge $e$ in a normal plane map (NPM) is the degree-sum of its end-vertices. An edge $e=uv$ is an $(i,j)$-edge if $d(u)\le i$ and $d(v)\le j$. In 1940, Lebesgue proved that every NPM has a $(3,11)$-edge, or $(4,7)$-edge, or $(5,6)$-edge, where 7 and 6 are best possible. In 1955, Kotzig proved that every 3-polytope has an edge $e$ with $w(e)\le13$, which bound is sharp. Borodin (1987), answering Erd\H{o}s' question, proved that every NPM has such an edge. Moreover, Borodin (1991) refined this by proving that there is either a $(3,10)$-edge, or $(4,7)$-edge, or $(5,6)$-edge.

Given an NPM, we observe some upper bounds on the minimum weight of all its edges, denoted by $w$, of those incident with a 3-face, $w^*$, and those incident with two 3-faces, $w^{**}$. In particular, Borodin (1996) proved that if $w^{**}=\infty$, that
is if an NPM has no edges incident with two 3-faces, then either $w^*\le9$ or $w\le8$, where both bounds are sharp.

The purpose of our note is to refine this result by proving that in fact $w^{**}=\infty$ implies either a $(3,6)$- or $(4,4)$-edge
incident with a 3-face, or a $(3,5)$-edge, which description is tight.