Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

? A graph is four colorable if and only if it is planar.

Is this true, I know that if a graph is planar it is four colorable, but is it true that if a graph is four colorable it must be a planar graph.

(EDIT) The following would have been a better way for me to have ask the question. What are the requirements for a graph to be planar? What are the requirements for a graph to be 4 colorable? Is there a simplification of the intersection of not planar and four colorable?

share|improve this question
No. The "utility graph" on the far left is not planar but is four colorable (in fact, two colorable): mathworld.wolfram.com/UtilityGraph.html –  Hunter Brooks Dec 28 '09 at 20:44
@unknown: I think people are downvoting your question because they feel like you didn't think about it enough before posting it. It's a fine question, but basically the very first example of a non-planar graph answers it. –  Anton Geraschenko Dec 28 '09 at 21:35
Perhaps another helpful comment: the first subdivision of any graph is two-colourable. So any topologically-defined class of graphs contains two-colourable examples. –  HJRW Dec 28 '09 at 22:17
I think the downvoting is rather harsh. The question is of interest to mathematicians and is clearly written (albeit with some misplaced punctuation). OK, so you know the answer to the question right off the top of your head? Good for you -- that's much of the point of MO. A substantial portion of the questions on this site are as obvious to someone as this is to you. Let's try to take smaller bites out of the novices... –  Pete L. Clark Dec 28 '09 at 22:29
@Pete: I'm not so sure in this case. It's very well-known that graphs are planar iff it does not have K_5 or K_3,3 as a minor, and moreover if you google "planar graph", the first hit is the wikipedia page, which contains this statement. Then it is very easy to see that K_3,3 is 2-colorable. –  Kevin H. Lin Jan 13 '10 at 1:58
show 4 more comments

1 Answer

up vote 10 down vote accepted

A graph is planar if and only if it does not have $K_5$ or $K_{3,3}$ as a minor. As Hunter's comment points out, $K_{3,3}$ is bipartite, ie two-colourable.

share|improve this answer
add comment

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.