Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.