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.
