13
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2013 at 5:05

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
3
  • 4
    $\begingroup$ Note that without the triangle-free assumption this method still proves the six-colour theorem. $\endgroup$ Jul 28, 2013 at 22:48
  • $\begingroup$ The colouring method in the second part is usually called `the greedy colouring' $\endgroup$ Jul 13, 2020 at 2:19
  • 1
    $\begingroup$ There is an error (may be typo) in the first part. It should not be strict inequalities eg: $4F/2\leq E$ and $4V/2\leq E$. $\endgroup$ Jul 13, 2020 at 2:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .