5
$\begingroup$

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?

$\endgroup$
15
  • $\begingroup$ 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? $\endgroup$
    – hardmath
    Apr 1, 2016 at 22:36
  • $\begingroup$ 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. $\endgroup$
    – Henry
    Apr 1, 2016 at 22:36
  • $\begingroup$ 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 $\endgroup$ Apr 1, 2016 at 22:37
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 1, 2016 at 22:46
  • 2
    $\begingroup$ 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"? $\endgroup$
    – bof
    Apr 1, 2016 at 23:51

2 Answers 2

5
$\begingroup$

The theorem is a statement about planar graphs. In the application to geography, you have a finite collection of "countries" (disjoint connected open subsets of the plane with, let's say, piecewise-smooth boundaries). Two countries are considered to be adjacent if the intersection of their boundaries has nonzero length. You then consider the graph with vertices corresponding to countries and edges between adjacent countries.

$\endgroup$
3
$\begingroup$

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$.

The map is the graph, and regions are the vertices.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .