1
$\begingroup$

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:

enter image description here

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.

$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Why would you need 3-connectivity here? $\endgroup$
    – hmakholm left over Monica
    Commented Apr 5, 2019 at 23:53
  • $\begingroup$ 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. $\endgroup$
    – Steve Kass
    Commented Apr 6, 2019 at 17:57
  • $\begingroup$ 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. $\endgroup$
    – hmakholm left over Monica
    Commented Apr 6, 2019 at 18:07
  • 1
    $\begingroup$ 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.” $\endgroup$
    – Steve Kass
    Commented Apr 7, 2019 at 17:45
1
$\begingroup$

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.

It is even mentioned on the Wikipedia page for vertex coloring:

"...Since a vertex with a loop (i.e. a connection directly back to itself) could never be properly colored, it is understood that graphs in this context are loopless."

$\endgroup$
3
  • $\begingroup$ It completely makes sense now, thank you :) $\endgroup$
    – ArsenBerk
    Commented Apr 5, 2019 at 23:14
  • $\begingroup$ It seems odd to say that the example graph is not face-colorable, and to need to appeal to the dual graph, which isn’t mentioned in the theorem. It seems clearer (see my answer) to say that the theorem applies only to maps, not to planar graphs in general. That avoids the unintuitive viewpoint that the example graph can’t be face-colored because one of its faces is adjacent to itself. $\endgroup$
    – Steve Kass
    Commented Apr 5, 2019 at 23:51
  • 2
    $\begingroup$ Instead of talking about duals, one could also word mostly the same argument by saying that the inner face is neighbor to itself because it is on both sides on the edge that sticks in. (And therefore it cannot possibly be colored differently than each of its neighbors). $\endgroup$
    – hmakholm left over Monica
    Commented Apr 5, 2019 at 23:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .