A non planar graph has either five vertices of degree at least 4 or six vertices of degree at least 3 (Without using Kuratowski's theorem)

Question

This was given as an exercise in my textbook before Kuratowski's theorem (a graph is non planar if and only if it has a subgraph homeomorphic to K$_5$ or K$_{3,3}$) was even introduced. So, there must be a simple intuitive solution to this problem. I was wondering if someone could help me solve this because I am not even close!

Answer 1

Assume, to the contrary, that our graph have no more than 5 vertices of degree at least 3 and no more than 4 vertices of degree at least 4.

1. Then all other vertices of the graph have degree at most 2.

2. The graph remains nonplanar if we remove vertices of degree 0 and 1.

3. If vertex $x$ of degree 2 is adjacent to vertices $u$ and $v$, then remove vertex $x$, but add edge $uv$. As a result the graph remains nonplanar.

4. Let us do operations 2 and 3 as long as there remain vertices of degree 2 or less in the graph.

5. As the result we will have graph with no more than 5 vertices, and no more than 4 vertices have degree at least 4.

6. It is easy to see that all graphs of order 5 or less, where at most four vertices have degree 4, are planar. (Say, if we remove one edge in $K_5$ we get a planar graph.) The contradiction follows.