# Graph theory question(about planar graphs, degrees)

Prove, that every planar graph, which has no loops or multiple edges, and has more than 3 vertices(it can be 3 too), has at least 3 vertices, which have 5 or less degree.

I kinda can't start this, I know that the minimal degree of a planar graph must be lower than 6, but I can't really prove this statement.

• Do you know about the Euler characteristic? – Michael Burr Mar 1 '15 at 14:12

I'll get you started. For a planar graph, the Euler characteristic formula (including the outer face) is $2=\#V-\#E+\#F$ where $\#V$ is the number of vertices, $\#E$ is the number of edges, and $\#F$ is the number of faces.
Assume the statement is false and that every vertex has degree at least 6. Fix $\#E$. Since each edge has exactly two endpoints, there are at most $\#E/3$ vertices. Since the smallest faces are triangles and each edge is a side of two faces (this uses that the graph is planar), it follows that $\#F$ is at most $\#2E/3$.
Combining all of these, it follows that $\#V-\#E+\#F\leq\#E/3-\#E+\#2E/3=0$. Therefore, there must be at least one vertex with degree less than 6.
If you continue the analysis, let $m$ be the number of vertices with degree at least 2 but not more than 5. In this case, the analysis above is unchanged, but the number of vertices is at most $\left(\frac{2\#E-2m}{6}\right)+m=\frac{\#E}{3}+\frac{2m}{3}$. Plugging this into the Euler characteristic formula, you find that $m$ is at least 3.