Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Consider the set of planar graphs where all the internal faces are triangles. If there is an interior point of odd degree the graph cannot be three colored. If every interior point has even degree can it always be three colored? Ideally I'd like a small counterexample.

share|cite|improve this question
up vote 25 down vote accepted

Yes, this is a corollary of the Three Color Theorem, see at the bottom here:

share|cite|improve this answer
Thanks. Do you have a reference for a proof? – Lance Fortnow Dec 30 '10 at 23:29
You might look at these two papers:… and… – Joseph Malkevitch Dec 31 '10 at 4:32
To add to Malkevitch's references: the equivalence of 3-colorability and even degree for planar triangulations is usually attributed to P. J. Heawood, "On the four-colour map theorem". Quarterly J. Pure Appl. Math. 29:270–285, 1898. However the papers Malkevitch linked have more to say about this attribution. – David Eppstein Dec 31 '10 at 5:59
Also, the corollary is not mentioned in Hull's notes, only the 3-color theorem itself. But from a 3-connected graph G with triangular internal faces and even internal vertices one can form a maximal planar graph 2G with even vertices simply by stitching two copies of G on the outer face. If G is not 3-connected, one can 3-color its 3-connected components independently. – David Eppstein Dec 31 '10 at 6:12

This result extends to high dimensions. A triangulation of a d-dimensional sphere so that every vertex has an even degree is (d+1) colorable. See, for example this paper: Jacob E. Goodman and Hironori Onishi, Even triangulations of $S^3$ and the coloring of graphs, Trans. Am. Math. Soc. 246 (1978), 501–510.

share|cite|improve this answer

Your Answer


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.