These days I've been reading about graph coloring. Right now I'm dealing with the five color theorem. I know how to prove that every planar graph is 6 and 5 colorable. I'm looking on the proof of the theorem:"Every planar graph can be 5-list colored".I've found a book and some pdf materials about this problem.The way they prove it is by using induction when two vertices are precolored but there are some things that I don't understand.
1.It takes the assumptions:
a)The cardinality of C(v)>=3 for all other vertices v of B
b)The cardinality of C(v)>=5 for all vertices v in the interior
I don't really understand why it takes these assumption.
For the first one I guess because in every circle if we have an odd number of vertices it will take us 3 colors to color the cycle and if we have and even number of vertices it will takes us 2 colors. But this is not always true if the vertices of the cycle are connected to other vertices outside the cycle for example:
So in these case we will need 3 or more colors and this is why the cardinality of C(v)>=3.
After these assumptions are taken it says :"Then the coloring of x,y can be extended to a proper coloring of G by choosing colors from the lists. In particular X(G)(indexed l)<=5"
Can anyone help me by giving a better explanation ?
The link to the pdf material: http://math.unco.edu/facstaff/Roberson/Docs/MATH%20695/5%20Color%20Theorem.pdf
There is a mistake in the figure for the case 1 because G1 and G2 are wrong positioned.
Thank you very much!