<p>This result is included in Ore's book <a href="https://www.elsevier.com/books/the-four-color-problem/ore/978-0-12-374571-2" rel="nofollow noreferrer"><em>The Four-Colour Problem</em></a> (see Theorem 7.4.3).</p>
<p>I saw a paper that states this as a folklore result and cites Ore. Interestingly, the book gives a different proof for (ii)<span class="math-container">$\implies$</span>(i). It seems that at that time, it wasn't known that the mapping <span class="math-container">$f\longmapsto f^*$</span> is a bijection.</p>
<p>Sorry to disappoint; but that's the best I could trace back.</p>

CC BY-SA 4.0
2020-07-01T10:53:18.710Z
2020-07-01T10:59:27.407Z
2020-07-01T10:59:27.407Z
Cyriac Antony
<p>Let <span class="math-container">$G$</span> be a maximal planar graph (also called a triangulation); i.e, <span class="math-container">$G$</span> is a planar graph every face of which is a triangle. It is well known that the following three statements are equivalent:<br />
(i) <span class="math-container">$G$</span> is 3-colourable<br />
(ii) dual graph <span class="math-container">$G^*$</span> of <span class="math-container">$G$</span> is bipartite<br />
and (iii) <span class="math-container">$G$</span> is Eulerian (i.e., every vertex has even degree).</p>
<p>I am interested in direct constructive proof of (i) <span class="math-container">$\iff$</span> (iii).<br />
<strong>I would like to know who came up with this proof; esp. the proof of (i)<span class="math-container">$\implies$</span> (ii) given below</strong></p>
<p>(i) <span class="math-container">$\implies$</span> (ii):<br />
Suppose <span class="math-container">$G^*$</span> has a 3-face colouring <span class="math-container">$f$</span> with colours 1,2,3. Then, one can obtain a 2-colouring <span class="math-container">$f^*$</span> of <span class="math-container">$G^*$</span> by assigning colour +1 at a vertex <span class="math-container">$v$</span> if colours 1,2,3 appear clockwise on faces around <span class="math-container">$v$</span>, and colour -1 at <span class="math-container">$v$</span> if 1,2,3 appear counterclockwise around <span class="math-container">$v$</span>. So, <span class="math-container">$G^*$</span> is bipartite.</p>
<p>David Gale wrote to Shen giving a proof for (i) <span class="math-container">$\iff$</span> (iii) using homology theory (for triangulations of the sphere). In that letter, he proves that the mapping <span class="math-container">$f\to f^*$</span> given in the proof above is in fact a bijection (answer to <a href="https://math.stackexchange.com/q/2719936/120721">this question</a> explains why). Shen explains these in <a href="https://link.springer.com/article/10.1007/BF03024801" rel="nofollow noreferrer">Mathematical Entertainments 20(3)</a>. I think that Gale's proof is different for the direction (i)<span class="math-container">$\implies (ii)$</span> (I am not sure, homology theory is Greek to me). I guess this proof should be known already because it is easier than the other direction. So, like I said, I would like to know who came up with this proof of (i)<span class="math-container">$\implies (ii)$</span> first.</p>
<p>Tsai and West's paper <a href="https://amc-journal.eu/index.php/amc/article/viewFile/193/124" rel="nofollow noreferrer">A new proof of 3-colorability of Eulerian triangulations</a> refer to Lovász (<a href="https://www.sciencedirect.com/book/9780444815040/combinatorial-problems-and-exercises" rel="nofollow noreferrer">Combinatorial Problems and Exercises</a>, Problem number is 9.52 I suppose) and to Shen (reference given above).</p>
<p>Thank you.</p>

CC BY-SA 4.0
2020-06-23T16:33:48.670Z
In a comment to this answer(https://math.stackexchange.com/a/2727059/120721), Misha Lavrov points out that Lovász attributes a proof of (ii) $\implies$ (i) to Whitney.
Cyriac Antony
<graph-theory><planar-graphs><graph-colouring><ho.history-overview>
Who proved that a triangulation is 3-colourable implies its dual is bipartite
Cyriac Antony
# Who proved that a triangulation is 3-colourable implies its dual is bipartite

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

Let $G$ be a maximal planar graph (also called a triangulation); i.e, $G$ is a planar graph every face of which is a triangle. It is well known that the following three statements are equivalent:  
(i) $G$ is 3-colourable  
(ii) dual graph $G^\*$ of $G$ is bipartite  
and (iii) $G$ is Eulerian (i.e., every vertex has even degree).

I am interested in direct constructive proof of (i) $\iff$ (iii).  
**I would like to know who came up with this proof; esp. the proof of (i)$\implies$ (ii) given below**

(i) $\implies$ (ii):  
Suppose $G^\*$ has a 3-face colouring $f$ with colours 1,2,3. Then, one can obtain a 2-colouring $f^\*$ of $G^\*$ by assigning colour +1 at a vertex $v$ if colours 1,2,3 appear clockwise on faces around $v$, and colour -1 at $v$ if 1,2,3 appear counterclockwise around $v$. So, $G^\*$ is bipartite.

David Gale wrote to Shen giving a proof for (i) $\iff$ (iii) using homology theory (for triangulations of the sphere). In that letter, he proves that the mapping $f\to f^\*$ given in the proof above is in fact a bijection (answer to [this question](https://math.stackexchange.com/q/2719936/120721) explains why). Shen explains these in [Mathematical Entertainments 20(3)](https://link.springer.com/article/10.1007/BF03024801). I think that Gale's proof is different for the direction (i)$\implies (ii)$ (I am not sure, homology theory is Greek to me). I guess this proof should be known already because it is easier than the other direction. So, like I said, I would like to know who came up with this proof of (i)$\implies (ii)$ first.

Tsai and West's paper [A new proof of 3-colorability of Eulerian triangulations](https://amc-journal.eu/index.php/amc/article/viewFile/193/124) refer to Lovász ([Combinatorial Problems and Exercises](https://www.sciencedirect.com/book/9780444815040/combinatorial-problems-and-exercises), Problem number is 9.52 I suppose) and to Shen (reference given above).

Thank you.

**Tags:** graph-theory, planar-graphs, graph-colouring, ho.history-overview

> **Comments:**
> **username_0**: In a comment to this answer(https://math.stackexchange.com/a/2727059/120721), Misha Lavrov points out that Lovász attributes a proof of (ii) $\implies$ (i) to Whitney.  

---

## 1 answers

### Answer by username_0 on 2020-07-01. Score: 2

This result is included in Ore's book [*The Four-Colour Problem*](https://www.elsevier.com/books/the-four-color-problem/ore/978-0-12-374571-2) (see Theorem 7.4.3).

I saw a paper that states this as a folklore result and cites Ore. Interestingly, the book gives a different proof for (ii)$\implies$(i). It seems that at that time, it wasn't known that the mapping $f\longmapsto f^\*$ is a bijection.

Sorry to disappoint; but that's the best I could trace back.


---

