Proving that a plane triangulation is 3-colorable iff it's even, using faces?

Question

My textbook gave the theorem that a plane triangulation is 3-vertex-colorable if and only if all its vertices were of even degree. It offered a proof using that the graph is 2-face-colorable, which I do not understand.

The book basically states that all the faces that were colored red would be labelled a, b, c clockwise, and all the faces colored blue would be labelled a, b, c counterclockwise, and that "this vertex coloring can be extended to the whole graph", thus proving the theorem.

I feel like I'm missing something because this doesn't really seem to be a proof so much as an example. Is there some theorem regarding "oriented" labels, or some name on this concept I can read up more on?

Answer 1

The intent is not to give an example, but to give an algorithm. That is, to prove that an even plane triangulation is $3$-colorable, it gives a procedure for $3$-coloring such a plane triangulation:

1. $2$-color the faces of the triangulation.
2. Pick an arbitrary face and label its vertices $a$, $b$, $c$ either clockwise or counterclockwise, depending on the color.
3. Pick an arbitrary face such that one of its vertices has already been colored. Complete its coloring using the color of that vertex and going either counterclockwise or clockwise depending on the color.
4. Repeat step 3 until all vertices have been colored.

However, this is still not a complete proof because it's not immediately obvious that this algorithm doesn't lead to a contradiction somewhere along the way. Maybe we go around the graph in one direction and give a vertex label $a$, but then go around the graph in another direction and the algorithm tells us to give an adjacent vertex label $a$, too.

(It is worth noting that if the algorithm does work, then the output depends only on the way that step 2 is done; steps 3 and 4 are forced. So the order in which we consider faces is not relevant.)

One way I've seen of extending this argument into a complete proof is to generalize it. We call a planar embedding of a graph a near-triangulation if all faces, except possibly the unbounded face, are triangles. The more general claim is that all near-triangulations in which all vertices not adjacent to the unbounded face have even degree, can be given a $3$-coloring (of the vertices).

For such graphs, we can prove that this algorithm works by an induction on the number of bounded faces. Given a graph, we must:

• Delete an edge along the unbounded face, getting a graph with fewer bounded faces.
• Apply the algorithm to this graph; we know it works by the inductive step.
• Put the edge back in. Prove that its endpoints have different colors, and that the face it creates is colored in a way that follows the algorithm.

Answer 2

Adding the details on Lavrov's beautiful proof of $3$-colourability of near triangulations whose internal vertices have even degree. Let $G$ be a near triangulation whose internal vertices have even degree. We may assume hereafter that $G$ is $2$-connected (otherwise work on the $2$-connected components). As noted by Lavrov, the proof is by induction on the number of internal faces.

Let $e := xy$ be an edge on the exterior face of $G$. There must be an internal face containing $xy$ ($G$ is $2$-connected). Let $z$ be the common neighbor of $x$ and $y$ forming the internal face $xyz$. There are three cases to consider:

1. $G$ is the triangle $xyz$. In this case 3-coloring is immediate.

2. $z$ is on the exterior boundary of $G$. In this case one among $x$ and $y$ - say $x$ must have degree 2, and $xz$ must be an edge on the exterior face of $G$. Consequently, $G \smallsetminus \{x\}$ must be a $2$-connected near triangulation with fewer internal faces, and must thereby admit an inductive $3$-coloring. Put $x$ back and a free color will be available to color $x$.

3. $z$ is an internal vertex. As $G$ is a near triangulation, there must be a wheel, say $W(z)$ in $G$ with $z$ at the center and an even number of vertices around $z$ (using the assumption that $z$ must have even degree). As there are three vertex disjoint paths in $W(z)$ between $x$ and $y$, it is not hard to see that $G \smallsetminus e$ is a $2$-connected near triangulation with fewer faces. Consequently,$G \smallsetminus e$ must be $3$-colorable (by induction hypothesis). The path from $x$ to $y$ in $G \smallsetminus e$ along the rim of $W(z)$ contains even number of vertices. Further, the vertices in the path must be $2$-colored (the color assigned to $z$ cannot be assigned to them). Consequently, $x$ and $y$ must be colored differently in $G \smallsetminus e$. Just put the edge $e$ back, and the coloring is complete!

To appreciate Lavrov's proof, you must read the story behind the problem presented in: https://faculty.math.illinois.edu/~west/pubs/eultri.pdf

Answer 3

1. "that a plane triangulation is 3-vertex-colorable if and only if all its vertices were of even degree". If ONE vertex has an odd degree you need 3 colours to colour the adjacent ones and a 4th colour for that vertex.
2. Colour the vertices of one triangle and give all opposite vertices the same colour. As all degrees are even this works always, for any (near-)triangulation.
3. Giving orientations (+1 or -1) to the triangles of any triangulation is the dual of a Heawoods vertex character for cubic graphs*. If the sum around each vertex is 0Mod3 then the graph is four-colourable. Giving alternate orientations around each even degree-vertex gives then always 0Mod3.

(*) See T.L.Saaty & P.C.Kainen,"The four-color problem" Dover 1986, page 120.