Proof for simple planar graphs using girth

Question

Question 3 For an $n$-vertex simple planar graph with girth $k$, prove that there are most $(n-2)\frac k{k-2}$ edges.

I have been having trouble with this question for a while. All I can think of is that if we know how many faces we have using the $v+f-e = 2$ formula then we can assume that every cycle in the graph is of length k in the worst case, and somehow go from there? But I'm just not able to put the pieces together. Any help would be greatly appreciated as I'm really struggling with this unit.

Answer 1

We can bound the number of edges using the girth. Let our graph have $e$ edges, $f$ faces, and $n$ vertices. Each of the graph's $f$ faces must have at least $k$ edges. Since each edge is contained in exactly $2$ faces, we have $2e \geq kf$. By Euler's formula, this is equivalent to $2e \geq k(2 + e - n)$. Some algebra gives us $$(k-2)e\leq (n-2)k \Rightarrow e \leq (n-2)\frac{k}{k-2},$$ as desired.

Answer 2

Pick a planar embedding of $G$ (which we may assume connected). If in this, $f_r$ is the number of faces with $r$ edges, then we have $2e=\sum rf_r\ge\sum kf_r=kf$. Using Euler, $$ ke+2k=kn+kf\le kn+2e$$ or, $$(k-2)e\le k(n-2), $$ whence the claim.