Kotzig's Theorem

Kotzig's theorem, published by Anton Kotzig in 1955 and popularized in the West during the 1970s by Branko Grunbaum, states that every polyhedral graph, meaning the graph formed by the vertices and edges of a convex polyhedron, has an edge whose two endpoints have a combined degree of at most 13. Kotzig originally stated the result in its dual form, that every convex polyhedron has two adjacent faces whose numbers of sides add up to at most 13; the triakis icosahedron shows the bound is tight, since no edge in it has a smaller combined endpoint degree than 13. The theorem does not extend to planar graphs in general, since complete bipartite planar graphs can have edges with unboundedly large combined endpoint degree, and later work has produced analogous bounds for planar graphs of higher minimum degree and for graphs embedded on higher-genus surfaces.