Let S be an independent set that is contained in any maximum independent set of graph$G = (V,E)$, prove that every maximum independent set of $G$ contains at least one vertex $w \in N(u)-N[S]$ for each child $u \in N(S)$.
Some explanation:
- The maximum independent set is an independent set in graph $G$ with the possible largest cardinality.
- For a set $X$ of vertices, let $N(X)$ denote the neighbors of $X$, i.e., the vertices $y \in V-X$ adjacent to a vertex in $X$, and denote $N(X)\cup X$ by $ N[X]$. Specifically, we use $v$ to denote the set $\{v\}$ of a single vertex $v$.
- For an independent set $S$ of $G$, a vertex $u\in N(S)$ is called a child of $S$ if it has a unique neighbor $s \in S$(i.e., $|N(u)\cap S|=1$), where $s$ is called the parent of $u$.
I've tried contradiction but failed. Could any one help me with this question?
Proof.
Choose some child $u\in N(S)$ with its parent $s\in S$. Let $M\subseteq V$ be a maximal independent set. We have $s\in M$ (because $S$ is by assumption contained in all maximal independend sets). If no vertex in $N(u)-N[S]$ is in $M$, then we can define the following other maximal independent set by replacing $s$ with $u$:
$$M':=M-s+u.$$
This works because all neigbors of $u$ are either $s$, or in $N(S)$, or in $N(u)-N[S]$, and none of these is in $M'$. However, $M'$ is a maximal independent set without $S\subseteq M'$, in contradiction to the choice of $S$.
$\square$
Maybe the following sketch can help to understand why this exchange is possible. The red vertices (and vertex sets) are part of the independent set. You can see that $u$ has (by assumption) no neighbors in the independent set except $s$.