1
$\begingroup$

Suppose that a connected planar simple graph with $e$ edges and $v$ vertices contains no simple circuit with length greater than or equal to $4.\;$ Show that $$\frac 53 v -\frac{10}{3} \geq e$$

or, equivalently, $$5(v-2) \geq 3e$$

  • 1
    I believe I've seen this before, just can't remember the proof off the top of my head, but $$5 \cdot v - 10 \geq 3 \cdot e$$ definitely looks familiar O_o...2011-06-20

2 Answers 2