# Perfect matching between max. size independent sets

$X$ and $Y$ are two max. size independent sets in a graph. Show that the subgraph $G[X \Delta Y]$ has a perfect matching.

What I've got: Take $A = X \setminus Y$ and $B = Y \setminus X$. Then $G[X \Delta Y]$ is a bipartite graph with color classes $A$ and $B$. Clearly, $|A| = |B|$. Furthermore, $\forall a \in A$, there must be at least one edge from $a$ to $B$ as otherwise $a$ could be added to $Y$, contradicting $X$'s maximum size. Similarly, $\forall b \in B$, there must be at least one edge from $b$ to $A$.

How do I proceed from here to prove the existence of a perfect matching between $A$ and $B$?

• Use Hall's theorem. – Chris Godsil May 1 '13 at 11:53
• But it isn't necessarily obvious that the size of the neighbor set of $A$ is larger than $|A|$ (and vice versa, for $B$), right? – wemblem May 1 '13 at 13:23
• If Hall's condition is not satisfied, you can produce a larger independent set. – Chris Godsil May 1 '13 at 14:14