Since we can match every agent as in case 1, a stable matching of \(M\)  exists and matches every agent [1]}. By looking at the reduced preference lists from the previous claim, it is clear that the two cases are the only possible ways to match every agents, unless some \(v_i, v_j\)  are paired to each other.
