Recall that a constricted set in a bipartite graph is a set of nodes S such that |N(S)| < |S|; for simplicity, we will only consider constricted sets S that are a subset of the RHS nodes (i.e., the set of students). Consider a bipartite graph with n nodes on each side that contains no perfect matching. For each question below, you must supply a proof if you answer true (or yes), and a counterexample if you say it is false (or no).

(a) (10pts.) True or false: Suppose such a bipartite graph (i.e., with no perfect matching) has more than one maximum matching. Then, there must be more than one constricted set.

(b) Consider bipartite graphs where the maximum size of a matching in the graph is strictly smaller than n1, i.e., every maximum matching leaves at least two students (and a corresponding number of rooms, of course) unmatched.

i. (5 pts.) Is each student who is unmatched in a maximum matching sure to belong to some constricted set of RHS nodes?

ii. (5 pts.) Consider any maximum matching in such a graph. Does an ABFS (Alternating Breadth First Search) starting from an unmatched RHS node on the RHS always yield a constricted set containing all unmatched RHS nodes (i.e., for all possible starting points, in all possible maximum matchings, in all such graphs)?