# A plane graph $G$ is $2-$face colorable if and only if $G$ is eulerian - counter example

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.

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.

• Why would you need 3-connectivity here? Commented Apr 5, 2019 at 23:53
• It’s possible the theorem is true with a weaker condition than $3$-connectivity, but based on a quick skim of literature, it seemed like $3$-connected graphs correspond to maps of “countries” (or polyhedra that could be flattened out into maps by making one face the unbounded country) in the most straightforward way. If you want to state a true theorem about maps of countries in the context of graph theory without making reference to duals, you should be able to consider the map as a graph whose edges correspond to the Jordan curves between points where three or more countries meet. Commented Apr 6, 2019 at 17:57
• Who says we're talking about "maps of countries" at all here? You're the only one insisting that it has to be narrowly about that, and I cannot see why you do that. Commented Apr 6, 2019 at 18:07
• I didn't say we were talking about maps of countries, just that perhaps we should be. The theorem in the question title is false. Or at best it is only true if one assumes an unusual and non-intuitive definition of “face-coloring.” I thought it would be helpful to provide a true theorem by restricting the statement to a useful subset of “plane graphs.” I suppose I could have said “A correct theorem is” instead of “The correct theorem is.” Commented Apr 7, 2019 at 17:45

If you look at the dual graph of your example, (to see how to color the faces) you see that you get a loop edge because of the pendant vertex in your original graph.

By definition, (at least from my book and other places such as here )a graph must not contain any loop edges in order to be colorable.