<p>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.</p>

CC BY-SA 2.5
2011-01-01T10:01:19.850Z
2011-01-01T10:01:19.850Z
Gil Kalai
<p>Yes, this is a corollary of the Three Color Theorem, see at the bottom here:
<a href="http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html">http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html</a></p>

CC BY-SA 4.0
2024-01-23T19:15:02.593Z
The link in the answer didn't go for me but I found it on the wayback machine:  [https://web.archive.org/web/20100614003714/http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html](https://web.archive.org/web/20100614003714/http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html)
Tyler Seacrest
CC BY-SA 2.5
2010-12-30T23:29:30.917Z
Thanks. Do you have a reference for a proof?
Lance Fortnow
CC BY-SA 2.5
2010-12-31T04:32:52.817Z
You might look at these two papers: http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBMQFjAA&url=http%3A%2F%2Fwww.math.uiuc.edu%2F~west%2Fpubs%2Feultri.ps&rct=j&q=coloring%20near%20triangulations&ei=sVsdTZz3HISClAe2k9HhDA&usg=AFQjCNHFOybQ5YRN-gZA8184kA1VfYxJ1w&cad=rja and http://www.google.com/url?sa=t&source=web&cd=7&ved=0CD8QFjAG&url=http%3A%2F%2Fwww.springerlink.com%2Findex%2Ffj3p5u5c3308fpbq.pdf&rct=j&q=coloring%20near%20triangulations&ei=sVsdTZz3HISClAe2k9HhDA&usg=AFQjCNGOvvteEMcJ5h4glsI47cB1lyeM1g&cad=rja
Joseph Malkevitch
CC BY-SA 2.5
2010-12-31T05:59:56.173Z
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
CC BY-SA 2.5
2010-12-31T06:12:01.353Z
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
CC BY-SA 2.5
2010-12-30T18:52:47.830Z
2010-12-30T18:52:47.830Z
domotorp
<p>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.</p>

<graph-theory><co.combinatorics><graph-colouring>
Coloring Planar Graphs
Lance Fortnow
# Coloring Planar Graphs

(Asked by: username_0 on 2010-12-30)

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.

**Tags:** graph-theory, co.combinatorics, graph-colouring


---

## 2 answers

### Answer by username_2 on 2010-12-30. Score: 26 | Accepted answer

Yes, this is a corollary of the Three Color Theorem, see at the bottom here:
<http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html>

> **Comments:**
> **username_0**: Thanks. Do you have a reference for a proof?  
> **username_4**: You might look at these two papers: http://www.google.com/url?sa=t&source=web&cd=1&ved=0CBMQFjAA&url=http%3A%2F%2Fwww.math.uiuc.edu%2F~west%2Fpubs%2Feultri.ps&rct=j&q=coloring%20near%20triangulations&ei=sVsdTZz3HISClAe2k9HhDA&usg=AFQjCNHFOybQ5YRN-gZA8184kA1VfYxJ1w&cad=rja and http://www.google.com/url?sa=t&source=web&cd=7&ved=0CD8QFjAG&url=http%3A%2F%2Fwww.springerlink.com%2Findex%2Ffj3p5u5c3308fpbq.pdf&rct=j&q=coloring%20near%20triangulations&ei=sVsdTZz3HISClAe2k9HhDA&usg=AFQjCNGOvvteEMcJ5h4glsI47cB1lyeM1g&cad=rja  
> **username_5**: 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.  
> **username_5**: 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.  
> **username_3**: The link in the answer didn't go for me but I found it on the wayback machine:  [https://web.archive.org/web/20100614003714/http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html](https://web.archive.org/web/20100614003714/http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html)  

---

### Answer by username_1 on 2011-01-01. Score: 24

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.


---

