# Planar Graphs with at least $2$ vertices and degrees at most $5$

I'm trying to study for my combinatorics exam and this was a suggested problem.

Let $G$ be a planar graph on $V\geq 2$ vertices. How can we prove that $G$ has at least $2$ vertices whose degrees are at most $5$?

Here are some things about planar graphs that I do know:

$V-E+F=2$

$E\leq 3V-6$

$3F\leq 2E$

-

Suppose every vertex, with at most one exception, has degree at least $6$. Do you know a relation between the degrees of the vertices of a graph and the number of edges? That, together with one of the relations you have written, should do it.

-
So would the at most one exception be less than 6? –  Wooooop Dec 8 '12 at 22:38
Suppose every vertex, with at most one exception, has degree at least 6. Then, 2E =< 2(3V-6) = 6V-12; Sum (deg V) >= 6(V-1) = 6V-6; We see that 6V-12 > 6V-6, thus there are at lease two vertices whose degrees are at most 5. Is this the solution? I still can't see how we have two vertices that are at most 5. –  Wooooop Dec 8 '12 at 22:43
On the hypothesis, the sum of the degrees is at least $6V-6$, so $E\ge3V-3$, contradicting $E\le3V-6$. Thus, the hypothesis fails; there must be more than one exceptional vertex. –  Gerry Myerson Dec 9 '12 at 6:30

Hint: Have you tried proving this by induction on $V$?

The objective is to prove $P(n) =$ "Any planar graph $G$ with $V \geq 2$ vertices, there exist two vertices of degree $\leq 5$." (You need to show that two distinct such vertices exist, and that will suffice.)

• $(1)$ Start with base-case: Show that for $G$ with $V = 2$ vertices, each vertex has degree 2. (That is, $P(2)$ is trivially true).

• $(2)$ Assume $P(k)$ is true when $V = k$.

• $(3)$ Then, show that if one more vertex is added to $G$, so $G$ has $V = k + 1$ vertices, it follows from $P(k)$ that $P(k+1)$ is also true.

Then you will have shown that $P(n)$ is true.

-