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.

  • $\begingroup$ Actually, Grötzsch's Theorem does even better: if $G$ is a planar triangle-free graph then $\chi(G) \le 3$. $\endgroup$ – A.S Aug 2 '13 at 5:05

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.

  • 3
    $\begingroup$ Note that without the triangle-free assumption this method still proves the six-colour theorem. $\endgroup$ – Chris Eagle Jul 28 '13 at 22:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.