= 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$, then
$$
gf\leq2e.
$$
Substitute $f=2-n+e$ from Euler's formula:
$$
g(2-n+e)\leq2e,
$$
and hence the <planar girth edge bound>
$$
\boxed{e\leq\frac{g(n-2)}{g-2}}.
$$
Back to article page
