Prove: If $G$ is a planar graph with $p$ vertices, $q$ edges, and finite girth $g$ then, $q \leq \frac{g(p−2)}{g−2}$ .

Question

Prove the following theorem: If $G$ is a planar graph with $p$ vertices, $q$ edges, and finite girth $g$ then, $$q \leq \frac{g(p−2)}{g−2}$$ .

I do not know how to go about proving this, besides the fact that I will probably have to use Euler's Theorems that $q=3p-6$ and $p-q+r=2$.

Answer 1

You have two equations: $q+2=p+r$ and $2q \geq g.r$ (Why?)

Eliminating you get the required result.

Edit: Why $2q \geq g.r$?

Construct a bipartite graph with the left (right) partition representing faces (edges) in your original graph. Two vertices in this bipartite graph are adjacent iff the corresponding edge lies in the corresponding face. Now count the edges in this bipartite graph. The edges coming out of the right partition are exactly $2q$. The edges coming out of the left partition is $f_1+f_2+... \ge r.g$, where $f_i$ is the number of edges in face $i$, $r$ is the number of faces and $g$ is the girth because girth is the least possible degree of one face. Then based on $\sum f_i=2q$ because one edge contribute 2 to the degree of the face totally, we have $2q \geq g.r$