Prove that every planar graph is $6$-choosable without using Thomassens's theorem
Thomassens's theorem: every planar graph is $5$-choosable
Now I'm kinda confused because if a graph is $5$-choosable then, it's $6$ choosable automatically, so is this a typo in the book and the question should be every planar graph is $5$-choosable?
Assuming this is not a typo, then I need to show that $\chi_l(G) = 6$ for every planar graph $G$.
I know that $G$ is a planar graph, so $G$ is $4$-colorable, so $\chi_l (G) \geq 4$. I also know that $m \leq 3n-6$ for $n\geq 3$ and $G$ must contain a vertex of degree $5$ or less.
I have the feeling that the info about $G$ must contain a vertex of degree $5$ or less will help me prove this but I can't get anything out of this except $\delta(G) \leq 5$, I wonder if anyone would tell me how is this related to $\chi_l(G)=6$?
Best Answer
It is very likely not a typo, as proving every planar graph is 5-choosable amounts to reproducing Thomassen's theorem, which may be too difficult for an exercise, whereas proving every planar graph is 6-choosable is rather simple.
You need to show that $\chi_l(G) \le 6$ for every planar graph $G$; as Thomassen's theorem shows, $\chi_l(G) = 6$ is false for every planar graph.
You can indeed use the fact that $G$ must contain a vertex of degree 5 or less to solve the problem. We prove the theorem by induction, i.e. we use induction the following statement:
Claim. A graph with $n$ vertices is 6-choosable.
Base case $n = 0$: A graph with no vertices is vacuously 6-choosable.
Inductive step: Assume the claim is true for all graphs with $n-1$ vertices. We will prove the claim for a graph $G$ with $n$ vertices. We choose a list assignment $L$ such that $|L(v)| \ge 6$ for all $v \in G$. We know that $G$ has a vertex of degree 5 or less; let $u$ be such a vertex. $G - u$ has $n-1$ vertices, so by the induction hypothesis $G - u$ is 6-choosable. Hence, we can color $G - u$ from $L$. Since $u$ is adjacent to at most 5 other vertices, and $|L(u)| \ge 6$, we can choose a color from $L(u)$ that is different from any adjacent color. So $G$ can be colored, and the theorem is proved.