Show that planar graph has at least 4 nodes of degree 5 of less

I am having a problem with this assignment. So the task says:

Show that every planar graph with at least 4 vertices has at least 4 
vertices of degree less than or equal to 5.

I know about the theorem stating that every planar graph has to have at least one vertex of degree 5 or less and that is shown by contradiction with the following inequality:

$3n-6 \ge m \ge 3n $

where $m$ is the number of edges and $n$ is the number of vertices, and I guess I should prove the above statement using this, but how?


Consider a maximally planar graph $G$ - that is, $G+e$ is not planar for any $e \not \in E(G)$. Note that proving that a maximally planar graph has at least 4 vertices of degree 5 or less is sufficient to prove that any planar graph has at least 4 vertices of degree 5 or less, since we could successively add edges to any planar graph to obtain a maximally planar graph. Now $G$ cannot have any vertices of degree 2 or less. If $G$ has a vertex $v$ of degree 0 or 1, we could add an edge from that vertex to another vertex in the face containing $v$, so $G$ is not maximally planar. If $G$ has a vertex $v$ of degree 2, there must be a face of length 4 or more, which you can add an edge to. So $\delta(G) \geq 3$.

Now suppose $G$ has at most 3 vertices of degree 5 or less. Then $2m \geq$ $6(n-3) + 3 \cdot 3$ $=$ $6n-9$. But since $m \leq 3n-6$, we have $2m \leq 6n-12$, a contradiction.


Assume to the contrary that no more than three vertices have degree 5 or less, so all but three have degree at least six. That mean $n \geq 6(m-3)+3 = 6m-15$ or $m \leq \frac{n+15}{6}$. But you have shown that $m \geq 3n$. Combining, we get $\frac{n+15}{6} \geq 3n$ or $17n \leq 15$, which is absurd.