$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$?

  • $\begingroup$ Use Hall's theorem. $\endgroup$ – Chris Godsil May 1 '13 at 11:53
  • $\begingroup$ 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? $\endgroup$ – wemblem May 1 '13 at 13:23
  • 1
    $\begingroup$ If Hall's condition is not satisfied, you can produce a larger independent set. $\endgroup$ – Chris Godsil May 1 '13 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.