Note: words in bold are good terms to search for in order to dig deeper and further your understanding!
​
Download a printable PDF handout!
​

Coloring maps

The problem of figuring out the fewest number of colors to color in any map was first formally stated in the 1800s. Mathematicians came up with proofs, but none of them turned out to be correct. This problem went unproven for over 100 years until in 1976, two researchers at the University of Illinois finally proved the four color theorem. This theorem states that any planar map can be colored in with just 4 colors. The proof was controversial at the time and historical nowadays because it was the first math theorem to be proven with computer assistance.

​

Creative math

The problem of coloring in a map is more formally called graph coloring, and is a problem inside of an area of math called graph theory. Graph theory is the study of webs (or networks) of data and how pieces of data connect to and relate to each other. Graph theory is categorized under the larger branch of discrete mathematics. Here a graph means one or more locations represented as a circle (a vertex) connected to each other in different ways with lines (edges). This type of graph is very different from the kind in geometry with an x and y axis, but they are both are similar in that they visualize something.

​

Computers

Graph coloring can be thought of a constraint satisfaction problem. A computer solves this problem by simply following a list of steps, like following a recipe in a cookbook. This list of steps is called an algorithm. Here are some steps taken from real algorithms to help you think like a computer:

  • Start with a state that touch lots of other states first. They are tricky to color in if other nearby states have already been colored in first.
  • Don't add another color unless you have to. Reuse colors as often as possible.
  • Color in states that have fewer color options left to choose from before coloring in states that have more colors left to choose from.

​

Applications

People need to solve these types of graph coloring problems to schedule planes at airports, figure out classroom schedules for teachers and students, let phones and computers to run multiple programs at once, create circuit boards, and to create and solve puzzles like sudoku.

​

How to study this more

Graph theory and graph coloring is usually taught as a part of a college class in discrete mathematics. Solving constraint satisfaction problems with algorithms is taught in computer science courses in algorithms as well as artificial intelligence. If you study computer science, mathematics, or engineering, you'll likely have an opportunity to study this subject more thoroughly.

​

Resources

Four Color Theorem - Numberphile (YouTube)
Graph Theory for Kids
Math for seven-year-olds: graph coloring, chromatic numbers, and Eulerian paths and circuits

Resources below this point assume a high level of mathematical maturity...beware of formulas and jargon!

Four Color Theorem (Wikipedia)
Discrete Mathematics: An Open Introduction (Free textbook)
DSATUR Algorithm for Graph Coloring (warning: code and computer science)



I presented this at the 2024 Michigan State University science festival along with Benyair Orellana, another computer science graduate student at Georgia Tech, as a way to introduce the public and prospective future scientists to a fun, interesting, and valuable type of math often not encountered until college. Because of its inherently visual nature (the "graph" in graph theory comes from the same Greek root as "graphics"), the intuition behind a lot of it is simple and accessible, even if you aren't a computer scientist!
I wanted to share an area of theory and math that is both fun and different from most people's conception of math. My hope is that participants will come away with a broader, more creative definition of mathematics and have a positive interaction with math while solving a complex equation with 50 states...er, I mean variables.