A Theorem About a Contractible and Light Edge
Zdenĕk Dvořák, Riste Škrekovski · SIAM Journal on Discrete Mathematics · 2006
In 1955 Kotzig [A. Kotzig, Math. Slovaca, 5 (1955), pp. 111-113] proved that every planar 3-connected graph contains an edge such that the sum of degrees of its end-vertices is at most $13$. Moreover, if the graph does not contain 3-vertices, then this sum is at most $11$. Such an edge is called light. The well-known result of Steinitz [E. Steinitz, Enzykl. Math. Wiss., 3 (1922), pp. 1-139] that the 3-connected planar graphs are precisely the skeletons of 3-polytopes gives an additional trump to Kotzig's theorem. On the other hand, in 1961, Tutte [W. T. Tutte, Indag. Math., 23 (1961), pp. 441-455] proved that every 3-connected graph, distinct from $K_4$, contains a contractible edge. In this paper, we strengthen Kotzig's theorem by showing that every 3-connected planar graph distinct from $K_4$ contains an edge that is both light and contractible. A consequence is that every 3-polytope can be constructed from tetrahedron by a sequence of splittings of vertices of degree at most $11$.