Prove that every planar graph without a triangle (that is, a cycle of length three) has a vertex of degree three or less. Then, prove that all planar graphs without triangles are four-colorable without using the four-color theorem.
This is a problem in my textbook that does not have a solution. How to approach this? Induction seems not to work.
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.
