FunTrivia Homepage New Questions Unanswered Post a Question Goto Qn # Archives

# What is the minimum number of colours required to draw a map so that no two adjacent regions have the same colour?

Kainantu

Even though we now know that 4 colors is enough to color any map, some maps can be colored with fewer colors--three colors or even two. Finding a method to determine exactly how many colors is needed for any map continues to daunt mathematicians today. Some mathematicians believe that a fast method to find out the minimum number of colors needed for a map is impossible (that is, it simply does not exist and hence can never be found).
This is widely regarded as the most important unsolved problem in computer science, mathematical logic, and the foundations of mathematics.

http://www.cs.uidaho.edu/~casey931/mega-math/workbk/map/mpbkgd.html

 May 20 04, 5:45 AM
kevinatilusa

Interestingly, that theorem only holds for the plane. If you got bored during breakfast and tried drawing a map on a doughnut (assuming it isn't jelly-filled), you could actually need as many as 7 colors.

[May 22 04 3:27 PM] kevinatilusa writes:

The place I got that from is a combinatorics textbook of mine by Van Lint and Wilson. I think it's called Heawood's conjecture/theorem or something similar (unfortunately, I don't have the book here with me).

 May 21 04, 3:57 AM
gmackematix

Some people think the Four Color Theorem in the plane is proved but this is quite controversial.
To find out more try the following:
http://www.math.gatech.edu/~thomas/FC/fourcolor.html

 May 22 04, 8:18 AM

### Other Similar Questions & Answers

 Have invited a couple friends over to share a pizza with me....Ok, there's 79 of us and, yep, one pizza. Pathetic as this may sound, what is the minimum number of cuts required to allow each of us to have a piece?

### Suggested Related FunTrivia Quizzes - 90,000 currently online

1 It's Not on the Map
 In legends, books, movies, TV, and video games, fictional countries are created for a variety of reasons - from adventure to satire. Here are a few of those creations.
Thematic 10Q Tough Tough
10 Q
illiniman14
Feb 05 11
399 plays
2 The As Have it
 The ayes have it. All these questions have to do with places that not only start with 'A' but also end with 'a'.
Alphabetical Places Average
10 Q
minch
Aug 15 00
6690 plays
3 And 'So' On
 The answers to the following questions all contain the word 'so' somewhere in the middle. Can you work out the answer from the clues given?
Words in Common Average
10 Q
rossian
Nov 20 10
186 plays

"Ask FunTrivia" is for entertainment purposes only, and answers offered are unverified and unchecked by FunTrivia. We cannot guarantee the accuracy or veracity of ANY statement posted. Feel free to post an updated response if you feel that an answer is inadequate or incorrect. Please thoroughly research items where accuracy is important to you using multiple reliable sources. By accessing our website, you agree to be bound by our terms of service.