<p>When you make deductions in this coloring problem you are following paths in the dual graph to the triangulation. Any inconsistency could be described by a cycle in the dual graph (a cycle of triangles linked edge-to-edge in the given maximal planar graph) such that, when you color one of the triangles (it doesn't matter which one or which coloring) and then propagate information around the cycle you come back to something different.</p>
<p>If you have a dual cycle that surrounds only a single primal vertex, then it's a wheel, and it's inconsistent if and only if it's an odd wheel.</p>
<p>If you have a dual cycle that surrounds more than one primal vertex, you can draw a dual path inside it that splits it into two dual cycles that each surround fewer primal vertices (this is where we use the fact that the triangulation is on the plane and not on a higher-genus surface). If both smaller cycles are consistent you could glue together consistent colorings of both to get a consistent coloring of the whole thing. So by induction on number of primal vertices contained, when the graph is Eulerian, all dual cycles are consistent.</p>

CC BY-SA 4.0
2020-07-19T05:42:42.077Z
Thank you for your answer. Of course, it was obvious to you, but not to me. I thought you did not give details because you were giving a known result and a short proof for it; but I could not trace how it worked.
Cyriac Antony
CC BY-SA 4.0
2020-07-20T07:46:46.723Z
Well, it is a known result at least. For instance it's an exercise in Bondy & Murty, Graph Theory with Applications (1976), p. 159. I don't remember my exact intent when I wrote that answer 10 years ago but it looks more like a description of the construction of a 3-coloring than a proof that the construction works.
David Eppstein
CC BY-SA 4.0
2020-07-18T16:58:11.463Z
2020-07-18T16:58:11.463Z
David Eppstein
<p>The key here is to note that the planar graph considered is <em>maximal</em>. Every vertex in this graph is adjacent to a triangle since every face of the graph is a triangle. Thus this is possible to extend the coloring on one triangle to the coloring of the entire graph since fixing two colors of the triangle forces the color on the third vertex. (Maybe look at this link for a similar response: <a href="https://math.stackexchange.com/questions/449811/planar-graph-with-maximum-number-of-edges-and-3-colouring-in-eulerian">https://math.stackexchange.com/questions/449811/planar-graph-with-maximum-number-of-edges-and-3-colouring-in-eulerian</a>)</p>

CC BY-SA 4.0
2020-07-19T05:39:51.280Z
Thank you for your answer. But, I am aware of this. I am asking how this serves *as a proof* that a 3-colouring is possible.
Cyriac Antony
CC BY-SA 4.0
2020-07-18T15:02:35.433Z
2020-07-18T15:02:35.433Z
Xin Yuan Li
<p>The following paragraph is from <a href="https://cstheory.stackexchange.com/a/1277/47855">this answer</a> by David Eppstein (emphasis mine).</p>
<blockquote>
<p>A maximal planar graph is 3-colorable iff it is Eulerian (if it is not Eulerian, then the odd wheel surrounding a single odd vertex requires four colors, and <em>if it is Eulerian then a 3-coloring may be obtained by coloring a triangle and then extending the coloring in the obvious way to adjacent triangles</em>).</p>
</blockquote>
<p>(A maximal planar graph is a graph with a planar embedding such that every face is a triangle).</p>
<p>I don't quite understand how emphasized part works as a proof. Let <span class="math-container">$G$</span> be a maximal planar graph. If <span class="math-container">$G$</span> is 3-colourable, then the 3-colouring is unique (upto swapping of colours) because in every diamond subgraph of <span class="math-container">$G$</span>, both degree-2 vertices of the subgraph should get the same colour. I suppose this suggests an algorithmic method for testing 3-colourability of <span class="math-container">$G$</span> namely (i) pick a triangle, (ii) give a 3-colouring to it arbitrarily, (iii) repeatedly extend it to adjacent triangles (assuming there is no inconsistency), and (iv) finally verify that the assignment is indeed a 3-colouring. If there is a vertex of odd degree, we will not succeed in assigning colour to all vertices. My question is this:-
<strong>How can we guarantee that the assignment will be consistent provided all vertices have even degree?</strong></p>
<p>Note: I don't see how Eulerian property (aka all vertices having even degree) ensures consistency of the assignment. I am asking this as a new question rather than a comment to the linked answer because he was answering a different question.</p>

<graph-theory><planar-graphs><graph-colouring>
3-colourability of Eulerian maximal planar graph
Cyriac Antony
# 3-colourability of Eulerian maximal planar graph

(Asked by: username_0 on 2020-06-22)

The following paragraph is from [this answer](https://cstheory.stackexchange.com/a/1277/47855) by David Eppstein (emphasis mine).

> A maximal planar graph is 3-colorable iff it is Eulerian (if it is not Eulerian, then the odd wheel surrounding a single odd vertex requires four colors, and *if it is Eulerian then a 3-coloring may be obtained by coloring a triangle and then extending the coloring in the obvious way to adjacent triangles*).

(A maximal planar graph is a graph with a planar embedding such that every face is a triangle).

I don't quite understand how emphasized part works as a proof. Let $G$ be a maximal planar graph. If $G$ is 3-colourable, then the 3-colouring is unique (upto swapping of colours) because in every diamond subgraph of $G$, both degree-2 vertices of the subgraph should get the same colour. I suppose this suggests an algorithmic method for testing 3-colourability of $G$ namely (i) pick a triangle, (ii) give a 3-colouring to it arbitrarily, (iii) repeatedly extend it to adjacent triangles (assuming there is no inconsistency), and (iv) finally verify that the assignment is indeed a 3-colouring. If there is a vertex of odd degree, we will not succeed in assigning colour to all vertices. My question is this:-
**How can we guarantee that the assignment will be consistent provided all vertices have even degree?**

Note: I don't see how Eulerian property (aka all vertices having even degree) ensures consistency of the assignment. I am asking this as a new question rather than a comment to the linked answer because he was answering a different question.

**Tags:** graph-theory, planar-graphs, graph-colouring

---

## 2 answers

### Answer by username_1 on 2020-07-18. Score: 3 | Accepted answer

When you make deductions in this coloring problem you are following paths in the dual graph to the triangulation. Any inconsistency could be described by a cycle in the dual graph (a cycle of triangles linked edge-to-edge in the given maximal planar graph) such that, when you color one of the triangles (it doesn't matter which one or which coloring) and then propagate information around the cycle you come back to something different.

If you have a dual cycle that surrounds only a single primal vertex, then it's a wheel, and it's inconsistent if and only if it's an odd wheel.

If you have a dual cycle that surrounds more than one primal vertex, you can draw a dual path inside it that splits it into two dual cycles that each surround fewer primal vertices (this is where we use the fact that the triangulation is on the plane and not on a higher-genus surface). If both smaller cycles are consistent you could glue together consistent colorings of both to get a consistent coloring of the whole thing. So by induction on number of primal vertices contained, when the graph is Eulerian, all dual cycles are consistent.

> **Comments:**
> **username_0**: Thank you for your answer. Of course, it was obvious to you, but not to me. I thought you did not give details because you were giving a known result and a short proof for it; but I could not trace how it worked.  
> **username_1**: Well, it is a known result at least. For instance it's an exercise in Bondy & Murty, Graph Theory with Applications (1976), p. 159. I don't remember my exact intent when I wrote that answer 10 years ago but it looks more like a description of the construction of a 3-coloring than a proof that the construction works.  

---

### Answer by username_2 on 2020-07-18. Score: 0

The key here is to note that the planar graph considered is *maximal*. Every vertex in this graph is adjacent to a triangle since every face of the graph is a triangle. Thus this is possible to extend the coloring on one triangle to the coloring of the entire graph since fixing two colors of the triangle forces the color on the third vertex. (Maybe look at this link for a similar response: <https://math.stackexchange.com/questions/449811/planar-graph-with-maximum-number-of-edges-and-3-colouring-in-eulerian>)

> **Comments:**
> **username_0**: Thank you for your answer. But, I am aware of this. I am asking how this serves *as a proof* that a 3-colouring is possible.  

---

