We saw in the lecture that \(M+I=n\) for \(n\)-vertex bipartite graphs with maximum matching size \(M\) and independent set size \(I\).
What is \(M+I\) in a graph consisting of a single cycle of length \(n\)? (You may find it helpful to give separate formulas for the cases when \(n\) is an odd number or an even number.)
What is \(M+I\) in a complete graph with \(n\) vertices?
Find a graph that is not bipartite but for which \(M+I=n\). (It may be easier to choose the matching and independent set first, and then add extra edges to form an odd cycle that does not interfere with the independent set.)
For the graph of courses and quarters on the first slide of the maximum matching lecture notes, find a maximum matching that matches CS161 to Spring 2022, and an independent set that includes all unmatched vertices and one vertex from each matched edge.
The lecture note slide "Hungarian algorithm in its simplest form" describes a version of the Hungarian algorithm that keeps the original graph edge weights unchanged, without adjusting them by heights. For this version of the algorithm, for the definition of the weight of an alternating path from this slide, and for the four paths chosen in the example slides at the end of the lecture notes, what are the weights of these paths? Compare the sum of these path weights to the sum of the weights of the edges used in the final matching.
Find an example of a stable matching input with three applicants and three employers, for which some applicant and some employer are matched to each other in every stable matching despite that pairing being the lowest preference for both of them. (Hint: choose the preferences so that the other applicants and employers can only be paired in one way.)
Explain why (regardless of how many applicants and employers are given and what their preferences are) it is impossible to have a stable matching where two applicant-employer pairs all get their lowest preference.