Connected planar simple Graph: number of edges a function of the number of vertices

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

• 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... – Nicolas Villanueva Jun 20 '11 at 15:55

As Joseph suggests, one of two formulas you'll want to use for this problem is Euler's formula, which you may know as

$$r = e - v + 2 \quad\text{(or}\quad v + r - e = 2)\qquad\qquad\quad (1)$$

where $r$ is the number of regions in a planar representation of $G$ (e: number of edges, v: number of vertices). (Note, for polyhedra which are clearly not planar, this translates into $r = F$, where $F$ is the number of faces of a polyhedron.)

Now, a connected planar simple graph drawn in the plane divides the plane into regions, say $r$ of them. The degree of each region, including the unbound region, must be at least five (assuming graph $G$ is a connected planar graph with no simple circuit with length $\leq 4$).

For the second formula you'll need: remember that the sum of the degrees of the regions is exactly twice the number of edges in the graph, because each edge occurs on the boundary of a region exactly twice, either in two different regions, or twice in the same region. Because each region $r$ has degree greater than or equal to five, $$2e = \sum_{\text{all regions}\;R} \mathrm{deg}(R) \geq 5r\qquad\qquad\qquad\qquad (2)$$

which gives us $r \leq \large\frac 25 e$.

Now, using this result from (2), and substituting for r in Euler's formula, (1), we obtain $$e - v + 2 \leq \frac 25 e,$$ $$\frac 35 e \leq v - 2,$$ and hence, we have, as desired: $$e \leq \frac 53 v - \frac {10}{3} \quad\iff \quad \frac 53 v - \frac{10}{3} \geq e \quad \iff \quad 5(v-2) \geq 3e$$

Try using Euler's "polyhedral formula" - If G is a connected plane graph then V + F - E = 2.