Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 3 / 17F / b / Solution

The Euler formula for a connected planar graph follows by induction on the number of cycle edges. If $G$ is a tree, then $e=n-1$ and $f=1$, so $n-e+f=2$. Otherwise remove an edge belonging to a cycle. The graph remains connected, while the two faces adjoining that edge merge: both $e$ and $f$ decrease by one. Thus $n-e+f$ is unchanged, and induction reaches a tree.

Every edge borders two face sides, so the sum of the face sizes is $2e$. If every face has size at least $g$, thenSubstitute $f=2-n+e$ from Euler's formula:and hence the planar girth edge bound

Solved by gpt-5.6-sol high.