# Number of faces of connected plane graph with cycles

Suppose $G$ is a connected plane graph with at least $g$ edges containing no cycles of length smaller than $g$, then if $f$ is the number of faces and $e$ is the number of edges then prove that $f \leq \frac{2e}{g}$.

I don't really know where to begin but the latter part of the question asks to prove that $e \leq \frac{g(v-2)}{g-2}$ which I can see is obtained from $f \leq \frac{2e}{g}$ and Euler's formula for convex polyhedra.. But any ideas how I could prove the first inequality?

HINT: The inequality is equivalent to $fg\le 2e$. Suppose that the faces are $F_1,\ldots,F_f$, and face $F_k$ has $e_k$ edges for $k=1,\ldots,f$. If we count the edges by face, we get $\sum_{k=1}^fe_k$.

• How many times does this sum count each edge?
• What is the relationship between each $e_k$ and the number $g$?
• I have a problem in that I can't find an example of a connected plane graph with no cycles of length smaller than g, without having only 2 faces. In which case this seems to show equality but if I attempt to create a third face on an arbitrary graph satisfying the conditions, then I seem to always create a smaller cycle and so violate the premise – user142702 Apr 20 '16 at 10:55
• @user142702: Take a regular hexagon, and draw three diagonals to divide its interior into $6$ equilateral triangles. You now have a planar graph with $7$ faces; $6$ have $3$ edges, and one has $6$ edges. If $g=2$ or $g=3$, this is an example matching the requirements of your problem. – Brian M. Scott Apr 20 '16 at 10:59
• So $\Sigma e_k$ counts each edge twice since every edge belongs to 2 faces and $g \leq e_k \forall k$ – user142702 Apr 20 '16 at 11:09
• @user142702: That’s right; and that gives you your inequality. – Brian M. Scott Apr 20 '16 at 11:10
• Ahhh I see so $g \leq e_k \Rightarrow fg \leq \Sigma_1^f e_k = 2e$, thank you ever so much – user142702 Apr 20 '16 at 11:14