Sign up ×

Show that a planar graph with $n$ vertices and $3n-6$ edges with $\chi=3$ is Eulerian.

$\chi=3$ means there is a optimal vertex colouring with three colours. Eulerian means that the graph admits an Eulerian cycle (a cycle which contains each edge exactly once).

My thoughts on this: I know that a planar graph has at most $3n-6$ edges and that a planar graph is maximal iff each face is a triangle. So in the present case each face is a triangle. Moreover it would suffice to prove that all vertex degrees are even since this is equivalent to being Eulerian. I don't see how the information that $\chi=3$ comes in.

share|cite|improve this question

1 Answer 1

up vote 2 down vote accepted

A graph is Eulerian if and only if each vertex has even degree.

So suppose there exists a vertex $v$ of odd degree in your graph. Now look at $v$'s neighbors. Since there are $3n - 6$ edges, the graph is maximally planar. That means that $v$ must have at least $3$ neighbors, and they must be connected in a wheel graph with $v$ at the center. Now what can you say about coloring a wheel graph with an odd length outer cycle?

share|cite|improve this answer

Your Answer


