I was studying a proposition about graphs, but there is an implication that I honestly don't understand. Let $\alpha(G)$ denote the indipendent number of G: to prove the thesis is said that given two maximum indipendent sets M and I (s.t. $|M| = |I| = \alpha(G)$) there exists a perfect matching between $M \triangle I$, which follows from Hall's marriage theorem.
Hall's Marriage theorem statement: Let G be a bipartite graph, $V(G) = X \cup Y$. There exists a perfect matching bewtween the two subsets if and only if $\quad \forall W \subseteq X \quad |W| \leq |N(W)|$ (where N(W) states for W 's open neighborhoods in G).
The theorem must be applied to $M \triangle I$ since $M \cap I$ could be non-empty.
It is true that
- $\forall x \in M \setminus I \quad \exists y \in I \setminus M$, otherwise $I \cup \{x\}$ would be an indipendent set with $\alpha(G) + 1$ nodes.
But how can I prove that these subsets satisfies the marriage condition? How can I rule out that, for examples $\nexists x,y \in M$ s.t. $|N(\{x,y\})|=1$? Any hint?
Thanks
Best Answer
My first instinct is to try to use contradiction.
Let $S$ be a subset of $M\setminus I$ and consider the neighbours of $S$ in $I\setminus M$ ( these are the same as the neighbours in $I$, since $M$ is independent) . Suppose there are less than $|S|$ of them.
What do we do now? We have to use the fact that $M$ and $I$ are maximum independent subsets and try to find a contradiction.
I think I see how to do it, we are going to build a larger independent set. One that works is $S \cup ( I \setminus N(S))$. So instead of taking $M = S \cup (M\setminus S)$ we replace $(M\setminus S)$ with the larger set $( I \setminus N(S))$. This set is independent because there is no edge between two vertices of $M$ or two vertices of $I$ and there is no edge between a vertex of $M$ and a vertex of $I$ because we are not taking any of the neighbours of $S$.