Approaches to Prove Every Planar Graph $G$ is $6$-colorable

coloringgraph theoryplanar-graphs

I have asked similar question in an earlier post, but this time I would like to get better understanding of the difference between using strong induction and regular induction to prove that every planar Graph $G$ is $6$-colorable.

My understanding: by induction hypothesis, for $n \ge 6$ and assume that every simple, connected and planner graph on up to $n$ vertices is $6$-colorable. Then we can not regular induction here because we have the connectivity condition, but if we removed connectivity condition from the assumption, then we could use regular expression. The issue here is if we delete a vertex $u$ from $G$, which might make the graph disconnected and this is why we need the strong induction and connectivity in the assumption.

Please let me know your thought of my understanding about proving every planar graph $G$ is $6$-colorable and why we need connectivity condition in the induction hypothesis.

Best Answer

There is no reason to require connectivity, it just makes your life harder.

There's one reason to try to stick to connected graphs, and that's probably why the source you're reading from does it: Euler's formula. We only have $|V(G)| - |E(G)| + |F(G)| = 2$ for a plane embedding of a connected planar graph, and this is the equation from which we derive $|E(G)| \le 3|V(G)| - 6$ (for graphs on at least $3$ vertices), which in turn lets us deduce that there is a vertex of degree less than $6$.

We can avoid this by observing that every planar graph can be turned into a connected planar graph by adding edges. Therefore if $|E(G)| \le 3|V(G)| - 6$ holds for all connected planar graphs on at least $3$ vertices, it holds for all planar graphs. Having deduced this, we can use this inequality with impunity and no care for whether our graph is connected.

But, if you want to prove the theorem for connected graphs, then we use strong induction, and say:

  • If the graph is connected, do the usual thing where you remove a vertex, color the remainder by the induction hypothesis, and put the vertex back.
  • If the graph is not connected, color every connected component by the induction hypothesis. (This is the part where we need strong induction: if the original graph has $n$ vertices, then the components can have any number of vertices between $1$ and $n-1$, so we need the induction hypothesis for all of those cases.)
Related Question