Number of faces of connected plane graph with cycles

335 Views Asked by At

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?

1

There are 1 best solutions below

6
On BEST ANSWER

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$?