Q1

Because of the incredible popularity of his class Math for Computer Science, TA Mike decides to give

up on regular office hours. Instead, he arranges for each student to join some study groups. Each group must choose a representative to talk to the staff, but there is a staff rule that a student can only represent one group. The problem is to find a representative from each group while obeying the staff rule.

a) Explain how to model the delegate selection problem as a bipartite matching problem. (This is a{modeling problem); we aren't looking for a description of an algorithm to solve the problem.)

b) The staff's records show that each student is a member of at most 4 groups, and all the groups

have 4 or more members. Is that enough to guarantee there is a proper delegate selection?

Explain.