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$?
  • $\begingroup$ 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 $\endgroup$ – user142702 Apr 20 '16 at 10:55
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Apr 20 '16 at 10:59
  • $\begingroup$ So $\Sigma e_k$ counts each edge twice since every edge belongs to 2 faces and $g \leq e_k \forall k$ $\endgroup$ – user142702 Apr 20 '16 at 11:09
  • $\begingroup$ @user142702: That’s right; and that gives you your inequality. $\endgroup$ – Brian M. Scott Apr 20 '16 at 11:10
  • $\begingroup$ Ahhh I see so $g \leq e_k \Rightarrow fg \leq \Sigma_1^f e_k = 2e$, thank you ever so much $\endgroup$ – user142702 Apr 20 '16 at 11:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.