Past exam of the mathematics course of the University of Cambridge / 2002 / ib / Paper 3 / 4E / Solution

For a connected cellular embedding on the sphere, the Euler formula for a connected planar graph isThe boundary graph of a convex polyhedron has such an embedding. Counting edge ends at vertices and edge sides at faces gives ${\sum }_{m\ge 3}m{V}_m=2E={\sum }_{n\ge 3}n{F}_n$. ThereforeFaces of size six contribute zero, and larger faces contribute negatively. The contribution of each triangle, quadrilateral or pentagon is at most three, soThus the small faces of a spherical polyhedral graph bound isThe tetrahedron shows that four is attainable. Connectedness and cellular faces are the standard hypotheses in this Euler formula; an arbitrary disconnected embedded graph has a different count.