There are 4 students trying to choose among 4 classes. Each student needs to take a single class to graduate. There is only one seat left in each class. Jon and Carlos both must take history to graduate. Alicia must choose between math, chemistry, or physics to graduate. Amanda must take physics to graduate.

1. What does a bipartite graph look like that represents students and the classes they can take to graduate.
2. Can you show the perfect matching, if there are anyIs there a perfect matching? Otherwise, find finding all the constricted sets is good.
3. If you found a perfect matching in (b), can you remove a single edge from the graph such that there is no longer a perfect matching? If so, remove the edge and find a constricted set in the new graph. Alternatively, if you didn't find a perfect matching in (b), can you add a single edge to the network such that there is perfect matching? If so, add the edge to the graph and show the perfect matching.