Prove the following theorem: If $G$ is a planar graph with $p$ vertices, $q$ edges, and finite girth $g$, then $q \leq g( p−2)/(g-2)$.
I realize this question was already asked, but it was answered in a very confusing way. If someone could be a little bit clearer on this it would be greatly appreciated. I'm just really not sure where to start the proof. I've done a bunch of small examples and I understand the relationship between $p, q$ and $g$. I'm just not sure how to go about proving it.
Thank you.
Pretty much any proof about counting vertices or edges in planar graphs starts with Euler's formula: $$v - e + f = 2$$ where $v$ is the number of vertices, $e$ the number of edges, and $f$ the number of faces. Or if we use your notation I guess we could call $r$ the number of faces and have $p - q + r = 2$.
In this case, we also know the girth $g$. This tells us that in particular, all the faces have at least $g$ sides. So if we add up the number of sides on each face, we get at least $gr$ in total. On the other hand, if we add up the number of sides on each face, we get $2q$, because each edge lies on two faces. (This sort of double-counting technique is also standard.) So $2q \ge gr$.
We want an inequality without $r$ in it, so eliminate $r$ by replacing it with $2 - p + q$, getting $$2q \ge g(2 - p + q)$$ which we can rearrange to $(p-2)g \ge (g-2)q$, or the inequality you wanted: $$q \le \frac{(p-2)g}{g-2}.$$