Question 2 (30 marks) The goal of this problem is to prove one of the multiple cases of the 4-colors theorem. Let our four colors be: red, blue,...

Question in the picture.

Discrete structures 2.

MATH 340 in McGill.

Question 2 (30 marks) The goal of this problem is to prove one of the multiple cases of the 4-colors theorem.Let our four colors be: red, blue, green and yellow. Assume that the 4—colors theorem is proven for all planar graphs with less than n verticesand that G‘ is a graph with n vertices that contains the subgraph below. We have alreadyremoved the four vertices in the middle, resulting in a smaller planar graph, and let theinduction hypothesis give us a coloring of the six outer vertices. Now suppose that thiscoloring is like in the following figure... (a) Use the Kempe—chain argument to show that we can modify the coloring to end upin one of the two following configurations. (b) Show that in either case, we can conclude that G‘ is 4-colorable. Hint: You may need to use another Kempe—chaz'n argument in one of the two cases...