(a) The final exam for a class must be taken in-person. However there are only 20 seats available in the classroom. To resolve this, the teacher decides to offer the final exam at four different times throughout the day. A student is allowed to choose what time they are available to take the final, but must submit at least two time slots out of the available four. (i) Model this as a bipartite matching problem. Specify what the vertices/edges should be and briefly describe what a matching means. (ii) Find the maximum number of students there can be in the class to guarantee each student has a seat for the final

regardless of which two time slots they choose. Prove this number is the maximum.

(b) There are n students in a class. Each day they are paired up, asked to research a topic, and then present the topic in the class. Only one students of the pair gives the presentation. The teacher then chooses the best presentation and gives that student an A for the class. Each day a student works with a different partner, and this continues for n1 days until each student has worked with every other student exactly once. The teacher claims it is possible for him to choose a different student every day for the best presentation. (i) Model this as a bipartite matching problem. Specify what the vertices/edges should be and briefly describe what a matching means. (ii) Prove that it is possible for the teacher to choose a different student every day for the best presentation.