Some (trivial?) doubts on the proof of chromatic number of any planar graph is at most 6

I am trying to show that chromatic number of any planar graph is at most 6. This is a weaker statement of the Four-Colour Theorem.

I have a vague idea about the proof but not sure how to convince myself that each statement of the proof really implies the next ones.

I used the fact that any simple planar graph has a vertex of degree at most 5. We then remove the vertex, then the remaining graph can be coloured with at most 5 colours (I am not sure on this part). If we add back the vertex, the graph can be coloured by at most 6 colours.

It seems to me that I am a bit confused how removing a vertex of degree at most 5 really does the job. Do we need to use induction somewhere? And how are we supposed to use induction?

I think about it like this: The fact that I used only says that a simple planar graph has a vertex of degree at most 5. But it may have a vertex of degree 6 or above right? The statement does not say all vertices have degree at most 5. Let say it has one vertex of degree 100. Then how can the chromatic number be at most 6?

I am still not very confident in proving graph theoretical statements.

Thanks.

• Use induction on the number of vertices. The chromatic number is defined by coloring vertices. If the graph is only a vertex of degree $100$ this graph is $2$-colorable: choose one colour for the distinguished vertex and another for the remaining ones.
– Pedro
Commented Jun 4, 2016 at 4:59
• @PedroTamaroff Yes you're right. But what if the graph is not only a vertex of degree 100? What if those 100 adjacent vertices are also adjacent to some other vertices, then it may no longer be 2 colourable, thus the chromatic number maybe more than 6? Commented Jun 4, 2016 at 5:39
• There's one part of the proof you've got wrong. It's not that the remaining graph can be coloured with at most 5 colours; it can be coloured with at most 6 colors (that's the induction). But that vertex you're trying to add back is only adjacent to 5 or fewer colours, so you can always pick a non-conflicting colour to assign to it. Commented Jun 4, 2016 at 7:12
• @user338393 You could also look at the proof this way: repeatedly delete the lowest-degree vertex from the graph, each time recording which vertex you deleted. Now play those back in reverse order. You can colour the vertices by a greedy method without ever getting stuck, as long as you colour the vertices in that specific order. Commented Jun 4, 2016 at 7:13

We do indeed need induction, otherwise there is no a priori reason for the graph with the vertex removed to be $6$-colorable.

Here is an example of such a proof.

First, note that all sufficiently small planar graphs are $6$-colorable. Certainly any graph with $|V|\le 6$ will be $6$-colorable. This establishes our base case.

Now suppose all graphs with $n$ or less vertices are $6$-colorable. Consider a planar graph $G$ with $n+1$ vertices. Since $G$ is planar, it must contain a vertex $v$ with degree at most $5$. Removing the vertex $v$ yields the graph $G\backslash\{v\}$, with $n$ vertices, which by the inductive hypothesis must be $6$-colorable. Now color $G\backslash\{v\}$ with $6$ colors and let's add back $v$. Since $v$ has at most $5$ neighbors, they take up at most $5$ colors. Then we can color $v$ the $6$th unused color to get a $6$-coloring of $G$. This completes the inductive step, so all planar graphs are $6$-colorable.

This is the idea of the proof (by induction on the number of vertices):

1. Base Case: Obviously any planar graph on 1 vertex is 6-colorable, so the base case is satisfied.
2. Inductive Step: Assume that every planar graph on $n$ vertices is 6-colorable. Now we have to prove it for every graph with $n+1$ vertices.
3. Now consider any Graph $G=(V,E)$ such that $|V|=n+1$. This is where the critical idea of the proof comes in: the existence of some vertex say $v \in V$ such that $deg(v) \leq 5$ in every planar graph.

Proof of this claim: Let $G^{'}=(V^{'},E^{'})$ be a planar graph.
Suppose on the contrary that $deg(v) \geq 6 \quad \forall v \in V^{'}$ Then, by the Handshake Lemma, $|E^{'}|=\frac{\sum_{v \in V^{'}} deg(v)}{2}$, but $\sum_{v \in V^{'}} deg(v) \geq 6|V^{'}|$, so $|E^{'}| \geq 3|V^{'}|$, which is a contradiction since $E^{'} \leq 3|V^{'}|-6$ for all planar graphs. Therefore $\exists v \in V^{'}$ such that $deg(v) \leq 5$.

4. Now that we know that for our arbitrary graph $G$ with $|V|=n+1$, $\exists v \in V$ such that $deg(v) \leq 5$.
Now, when we consider the graph $G \setminus v$ (Original graph without the vertex with degree less than equal to 5), the vertex set of this graph has $n$ vertices since the vertex set is $V \setminus v$. Now, by our induction hypothesis, this graph $G \setminus v$ is 6-colorable.
Now, when we consider all the neighbors of $v$ in $G$, we see that they can take up at most 5 colors since there are only at most 5 neighbors (And we know a coloring exists since we assumed all graphs with $n$ vertices have a 6-coloring). Therefore, we can simply color $v$ with a color different from its neighbors and we obtain a 6-coloring for the graph $G$, and since this is true for any arbitrary $G$ with $n+1$ vertices, we have proven the result by mathematical induction.

To address your specific concerns: "I think about it like this: The fact that I used only says that a simple planar graph has a vertex of degree at most 5. But it may have a vertex of degree 6 or above right? The statement does not say all vertices have degree at most 5. Let say it has one vertex of degree 100. Then how can the chromatic number be at most 6?"

Yes, the statement only shows that there exists a vertex with degree less than equal to 5; there very well maybe vertices with degree 100 in the graph. Such planar graphs that have vertices with degree 100 are still 6-colorable since all its neighbors need not have 100 different colors.
For example, consider the graph $K_{1, 100}$, a complete bipartite graph where 100 vertices have degree 1 and 1 vertex has degree 100. The vertex with degree 100 can be colored with 1 color and every other vertex can be colored with another color. So clearly, the chromatic number for this graph is 2, which is less than 6. This example is obviously not enough to show it for all graphs, but it gives you an idea of how a planar graph with a vertex of large degree can still be colored.

Kempe’s proof is actually fairly straightforward! We give it here.

Proof. We proceed by contradiction. Assume not: that there are planar graphs on finitely many vertices that need at least 5 colors to be colored properly. Consequently, there must be some smallest planar graph G, in terms of the number of its vertices, that needs at least five colors to color its vertices! Pick such a graph G. Notice that if we remove any vertex v from G, we have a graph on a smaller number of vertices than G. Consequently, the graph G \ {v} can be colored with four colors! Let v be the vertex in G with degree at most 5. Delete v from G: this leaves us a graph that we can four-color. Do so.