# Showing a certain class of graphs has minimum degree at most 4

I found the following question in a previously assigned graph theory final:

Let $G$ be a simple, planar graph with $1\leq |E(G)|< 30$. Show that $G$ has a vertex with degree at most 4.

My Attempt: this is equivalent to showing $\delta(G)\leq4$. Assume by contradiction that $\delta(G)\geq 5$. First, we know

$$5|V(G)|\leq \sum_{v\in V(G)} \text{deg}(v) \leq 2|E(G)|.$$

Also, since $G$ is planar we must have

$$|E(G)|\leq 3|V(G)|-6,$$

which implies

$$\frac{5}{2}|V(G)|\leq|E(G)|\leq 3|V(G)|-6.$$

From here I am lost. Are there any suggestions for how to continue, or is this not leading to a solution?

-

Using the fact that $|E(G)| < 30$ gives $\frac{5}{2} |V(G)| < 30$ or $|V(G)| < 12$.

Using the fact that $\frac{5}{2} |V(G)| \leq 3 |V(G)| - 6$ implies $|V(G)| \geq 12$.

Finished.

And here's a picture of a graph with exactly 30 edges that is planar and 5-regular.

http://math.stackexchange.com/a/162418/8671

-
you are right, I wrote it down incorrectly. –  Holdsworth88 Sep 21 '12 at 14:55