If you have a coloring book with a map that includes all the US states, how many different colors would you need in order to color all the states to make sure that the same color never touches itself? The four color theorem states that in a given plane, the regions can be colored using at most 4 colors so that no two adjacent regions (or states that share a border) have the same color. This theorem was proven in 1976 and was one of the first major theorems to be proven using a computer.