# What is a "map" in the four color theorem?

The four color theorem declares that any map in the plane (and, more generally, spheres and so on) can be colored with four colors so that no two adjacent regions have the same colors.

However, it's not clear what constitutes a map, or a region in a map. Is this actually a theorem in graph theory, something about every planar graph with some properties admitting a certain coloring?

Or does one really prove it using regions in the plane (which I guess we take to have non-fractal boundaries, or something). What is the precise definition?

• A planar graph is a simple graph that can be drawn in the plane, so that edges between nodes are represented by smooth curves that meet only at their shared endpoints (nodes). Such graphs have well-defined "faces" which are the regions colored under the conditions of the four color theorem, i.e. regions with a shared edge along their respective boundaries are colored distinctly. Are these the ideas that you needed to have explained in greater detail? Apr 1, 2016 at 22:36
• Here map probably takes its geographical meaning, and is a loose use of words. Adjacent regions (those that share an edge) have to have different colours. Apr 1, 2016 at 22:36
• Well, maybe. Is the theorem about all planar graphs? Or regions in the plane satisfying certain axioms? I just want to know what "map" means precisely in this context Apr 1, 2016 at 22:37
• @hardmath: The geometric interpretation breaks down in this case -- but the theorem does still hold in the sense that there's a valid four-color assignment to any graph whose every finite subgraph is planar. Apr 1, 2016 at 22:46
• Actually, if a map "can be colored with four colors so that no two regions have the same colors," then the map has at most four regions. Did you mean to say "adjacent regions"?
– bof
Apr 1, 2016 at 23:51

Here is a formal statement. Let $G=(V,E)$ be a finite planar graph with vertices $V$ and edges $E$. It is possible to find a collection $P=\{S_1,S_2,S_3,S_4\}$ of dijoint subsets of $V$ such that $V=S_1\cup S_2\cup S_3\cup S_4$ and for every $a,b\in S_i$, there is no edge in $E$ joining $a$ and $b$.