Actually, proof is asked in here: Planar graph has an euler cycle iff its faces can be colored with 2 colors. But my question is not about proof but about why is the following graph not a counter example:
I read the definition of eulerian graph in the book and looked it up in Wikipedia but both says eulerian graph is a graph that contains eulerian cycle (or tour) or a graph with every vertex of even degree. So, above graph is a plane graph and 2-face colorable, but it does not contain eulerian cycle. As I saw in here, above graph is semi-eulerian as it contains an eulerian path but not an eulerian cycle. So why this graph is not a counter example for the argument in the title? Thanks in advance.
Best Answer
The theorem as you stated it isn’t true, as your example shows. I think the correct theorem is “A map $G$ is $2$-face colorable if and only if $G$ is Eulerian.” A map (not to be confused with a “map graph”) is a $3$-connected planar graph. It’s possible the theorem can be corrected in a different way be redefining what a face-coloring is, but I’m more comfortable saying that your example is not a map than saying that your example is not face-colorable.