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?
Best Answer
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:
$G$ is the triangle $xyz$. In this case 3-coloring is immediate.
$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$.
$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