Let G be a connected planar graph with all circuits of length of at least k.

Prove that the inequality e <= 3v - 6 with e = number of edge and v = number of vertex can be expanded into e <= (k/k-2)(v-2)

Printable View

- Sep 12th 2007, 03:42 PMtttcomraderPlanar Graph problem
Let G be a connected planar graph with all circuits of length of at least k.

Prove that the inequality e <= 3v - 6 with e = number of edge and v = number of vertex can be expanded into e <= (k/k-2)(v-2) - Sep 15th 2007, 12:26 AMOpalg
Hint: look up the proof of the inequality $\displaystyle e \leqslant 3v - 6$. All it needs is a slight adaptation to the case where each face of the graph has at least k edges.