Show that triangle-free planar graphs are four-colorable

Solution 1:

For the first part we can use Euler's $F-E+V=2$, where $F$ is the number of faces (counting the face that includes $\infty$), $E$ is the number of edges, and $V$ the number of vertices.

If there are no triangles then each face is enclosed by at least $4$ edges. So $4F/2<E$, i.e. $F<E/2$. From this we get $V>E/2+2$. If all vertices have order $\geq4$ then $4V/2<E$, i.e. $V<E/2$. From this we get $0>2$. So, we cannot have no triangles and at the same time all vertices with degree $\geq4$.

For the second part take a vertex that has degree $\leq3$. Color it and its neighbors with different colors $A,B,C,D$. We can do this only because it has degree $\leq3$. We can delete this vertex and the edges insident on it. If we color the rest of the graph there is always a way to color the deleted vertex. Notice that the graph with this vertex deleted still has no triangles, but less vertices. Apply induction on the number of vertices now.