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 explains why). Shen explains these in Mathematical Entertainments 20(3). 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 refer to Lovász (Combinatorial Problems and Exercises, Problem number is 9.52 I suppose) and to Shen (reference given above).

Thank you.


This result is included in Ore's book The Four-Colour Problem (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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.