The 4-Color theorem is a mathematical theorem that states that any 2D map (like, say, a geographical map) can be completely color-coded such that no two adjacent regions share the same color, by using only four different colors for the entire map.
The goal of this project was to assess the following: starting with an infinitely large random map, if I were to change the color of just one region, how many other adjacent regions must I also change (on average) in order to return the map to being properly 4-colored?
By changing the color of one state, I must also then change the color of neighboring states which share its new color, thus prompting me to change the color of those states’ neighboring states, et cetera.
I wrote a script in Python to try and answer this question. To do so, it generated a very large random map, colored it, altered the color of one state, and then recursively recolored the map until it found an optimal solution. (One such solution is pictured in the animated gif above.)
So, what’s the answer? After averaging several thousand trials, it turns out that around seven regions need to be re-colored in order to restore the proper coloring of the map.
Now you know.
Derek A. Wood 