Map coloring is an application of Graph Theory, the study of graphs. A graph is informally a collection of points, known as vertices, connected by lines, known as edges. Two vertices connected by an edge are said to be adjacent. A graph is planar if it can be drawn with no edges overlapping each other, as shown in the diagram to the left.

Graphs are useful to analyze map colorings because a map containing only connected territories can easily be converted into a planar graph by representing each territory with a vertex and each border segment with an edge, as in this page's main image. An edge is not drawn between two territories that share only a corner, such as between Utah and New Mexico. The four color theorem states that the vertices of any planar graph can be colored with at most four colors such that no adjacent vertices are the same color. Since maps can be represented by planar graphs, this theorem is equivalent to saying any map with only connected territories can be colored with at most four colors, such that no territories of the same color will share a border segment.