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

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.

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.)
• Thank you for the answer. Can you please explain more what do you mean by "which in turn lets us deduce that there is a vertex of degree less than 6."?
– Avv
Commented Nov 30, 2020 at 20:04
• I was skipping over that step because I assume that you understand the overall idea of the proof, and just want to know how the induction works. Is that not true? Commented Nov 30, 2020 at 20:20
• Yes, I got you now. Thanks. What is the different compared to regular induction? Can not regular induction handle disconnectivity case if we remove a vertex from the graph?
– Avv
Commented Nov 30, 2020 at 20:38
• The part where we remove a vertex can be handled by regular induction. We need strong induction when we say "color every connected component by the induction hypothesis", since the connected components can be considerably smaller than the original graph. Commented Nov 30, 2020 at 21:08
• In the proof by strong induction, even if we start with a connected graph $G$, when we remove a vertex $v$, $G-v$ might not be connected. Commented Nov 30, 2020 at 22:55