We first show that every agent is matched in any stable matching. We can always match the agents in a given group as in the case 1, and this matching will be stable. By [1]} the set of matched agents is the same for every stable matching, so we know that every agent must be matched for a matching to be stable.
