Can someone please clarify this proof of the five-color theorem?

Question

I am having trouble following this proof of the five-color theorem: http://www.unco.edu/nhs/mathsci/facstaff/roberson/Docs/MATH%20695/5%20Color%20Theorem.pdf. (The proof is from pages 1-4.) In particular, I do not understand Case 2 of the inductive step.

To give a little background info without following the link, I think the author is trying to show that the boundary of any planar graph can be 3-colored while its interior vertices can be 5-colored. He proves this statement is true by strong induction over the number of vertices. For Case 1 of the inductive step, he shows it is true for graphs with chords. For Case 2, he shows it is true if boundary nodes are connected to interior nodes. Here is the text of the confusing part of Case 2:

This $G'$ has an outer boundary defined by the following $B' = (B\setminus\{v_0\}) \cup \{v_1, v_2, \dots, v_t\}$. We know by our second assumption that $|C(v_0)| \geq 3$, and that there must exist two colors $\gamma$ and $\delta$ in $C(v_0)$ that are different from $\alpha$. Now we want to remove the colors $\gamma$ and $\delta$ from the color sets for each of the vertices $v_1, \dots, v_t$ since we know that $v_0$ will have one of those two colors. Thus, we can think that if $C(v_i)$ was the original color sets for the vertices $v_1, \dots, v_t$, their new color sets will be of the form $C(v_i) \setminus \{\gamma, \delta\}$. The remaining vertices in $G'$ that did not share a common edge with $v_0$ may maintain their original color sets in $G'$. Now $G'$ satisfies all three of our assumptions, and is therefore 5-list colorable by induction. Then we can return to our graph $G$ and choose $v_0$ to be color $\gamma$ or $\delta$, a color different from $w$, and show that $G$ must also be 5-list colorable.

• Why are vertices in $G$ that did not share an edge with $v_0$ allowed to keep their color? We haven't proven the hypothesis for $G$, so what if they are colored with a color that isn't $\alpha$, $\beta$, $\delta$, or $\gamma$? Then adding $v_0$ back would mean $G$ has 4 colors on its boundary.

• If $w$ is colored $\gamma$ or $\delta$, and $v_0$ is added back, then wouldn't $w$, $v_0$, $x$, and $y$ be 4 different colors?

• What exactly is the color set of a vertex?

• Why can we simply say $v_1, \dots, v_t$ are different colors than $v_0$? Don't we have to prove that's possible? Why can't we also say $w$ is a different color than $v_0$?

I'm simply left really, really confused by this proof, even after looking through the examples. I've searched online for another version, but this appears to be the only one. Can someone clarify the above points, or, ideally, reexplain Case 2?

Answer 1

I think most of your confusion is cleared up by understanding what list coloring is.

The ordinary five-color theorem just says that if we have $5$ colors to work with, we can color any planar graph. The list five-color theorem says something stronger: if we give each vertex in a planar graph a color set of five colors (which don't have to be the same for every vertex) then we can color the graph by giving each vertex a color from its color set.

The list five-color theorem implies the ordinary five-color theorem: we could just give each vertex the same color set.

The reason we want to use list coloring for this problem is that it makes incremental progress easier and more gradual. Rather than saying "we will color this vertex red", which is a very bold step, we say "we will eliminate the color green from this vertex's color set".

Specifically, at the point in the proof where you're confused (though you may want to re-read all of it with the correct definition in mind), we have:

• A graph $G$ which is triangulated except for the outer boundary;
• Two adjacent vertices $x$ and $y$ on the outer boundary whose colors we've decided completely;
• The rest of the vertices on the outer boundary have their color sets reduced to $3$;
• The interior vertices still have color sets of size $5$.

(The point of doing it this way is that it's a stronger hypothesis we use for the induction. Starting from an arbitrary graph with color sets of size $5$ on every vertex, we may reduce the color sets along the outer boundary arbitrarily to put it into this form.)

One thing we don't promise is that the outer boundary is going to be $3$-colored in the end: the color sets on the outer boundary all have size $3$, but they might not all be the same set of size $3$. I think several of your questions are just misunderstandings of this.

To summarize what happens in Case 2:

1. We pick two colors $\gamma, \delta$ that are in $v_0$'s color set but not equal to $\alpha$, the color of $x$. (This is possible since $v_0$ had a color set of size at least $3$ to begin with.)
2. Now we consider the graph $G'$ with $v_0$ removed; it has the same outer boundary as $G$ except with $v_1, v_2, \dots, v_t$ taking the place of $v$.
3. In $G$, $v_1, \dots, v_t$ all had color sets of size $5$: they were in the interior. So we remove $\gamma$ and $\delta$ from these color sets, and now they still have color sets of size at least $3$: this is okay for boundary vertices.
4. By induction, we can color $G'$ while satisfying these constraints.
5. We can assign $v_0$ one of the colors $\gamma$ or $\delta$ because, of $v_0$'s neighbors, only $w$ could possibly have used one of these colors - and $w$ can't be using both.

Note that we couldn't have said "remove $\gamma$ and $\delta$ from $w$'s color set" because, in $G$, $w$ already has a color set of size only $3$. Removing $\gamma$ and $\delta$ might be equivalent to deciding $w$'s color, which is a stronger condition than our induction hypothesis allows for.