Question

please answer all parts i give you good feedback

Question 1 (15 marks) Suppose that in a group of 100 boys and 100 girls there is a boy B, such that B is second highest on every woman's preference list.Is possible that, in every stable matching, B ends up with the girl he likes le ast of all? If yes, give an example, if not, prove it. Questio n 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 pl anar graphs with less than n vertices and that G is a graph with n vertices that contains the subgraph below. We have already removed the four vertices in the middle, resulting in a smaller pl anar graph, and let the induction hypothesis give us a coloring of the six outer vertices. Now suppose that this coloring is like in the following figure.. (a) Use the Kempe-chain argument to show that we can modify the coloring to end up in one of the two following configurations. or (b) Show that in either case, we can conclude that G is 4-colorable Hint: You may need to use another Kempe-chain argument in one of the tuo cases..

Answer 1

0 aston: Given that, Girlg hag a a Solumatis) ho Eacb 0 fal tibu oru tule 99