163 students only: For \(n\)-vertex bipartite graphs, we have seen that if \(M\) is the size of the maximum matching, and \(I\) is the size of the maximum independent set, then \(M+I=n\). Describe a construction for a non-bipartite graph on \(n\) vertices for which \[M+I=\left\lfloor\frac{n}{2}\right\rfloor+1.\] What are the values of \(M\) and \(I\) for your graph?
265 students only: Prove that for all graphs, \[M+I\ge\left\lfloor\frac{n}{2}\right\rfloor+1.\]
Find a polygon with horizontal and vertical sides for which the bipartite graph of 2-vertex cuts that touch or cross, described in the lecture notes, is the six-vertex bipartite graph shown below. How many rectangles are required for a partition of your polygon into the minimum number of rectangles?
How many perfect matchings does the complete bipartite graph \(K_{3,3}\) have?
Find an assignment of weights for the nine edges of \(K_{3,3}\) so that there is a unique minimum weight perfect matching, there is a unique maximum weight perfect matching, and there is an edge used by both of these matchings. (Hint: you only need to use 0, 1, and 2 as your edge weights, although you are allowed to use other weights. You can describe your weight assignment by drawing the graph and labeling its edges, or you can use a chessboard-like diagram like the \(4\times 4\) example in the lecture notes.)
Suppose that we form a stable matching input from the \(4\times 4\) example in the lecture notes for weighted matching, by setting the preferences for each vertex to be ordered from smaller weights to larger weights. For instance, because the top red vertex has edges to its neighbors with weights 5, 9, 17, 21, its top preference would be for the neighbor with weight 5, its second preference would be for the neighbor with weight 9, etc. For these preferences, is the minimum-weight matching computed in the example a stable matching? Explain why or why not.