Lesson 2

Matchings in bipartite graphs are used as a mathematical model for a wide variety of practical problems: assigning students to rooms, patients to hospitals, requests to servers, and so on.

Problem. The table below shows which of the six rooms are liked by each of the six students. What is the maximum number of students that can be assigned to rooms they like? (No more than one student per room.) Try it!