Prove that $I$ is a Maximal Independent Set of $G(V,E)$ if and only if $V\setminus I$ is a Minimal Vertex Cover of $G(V,E)$.
I think that I have managed to prove that the complement of $I$ is a vertex cover, but I'm having trouble proving that it is the minimal vertex cover.
My proof so far is:
=> Assume that $I$ is a maximal independent set on $G(V,E)$. Then for every edge $e \in E$, there exists an $i \in I$ and a $j \in V\setminus I$ such that $e=(i,j)$. Thus, $V\setminus I$ forms a vertex cover of $G(V,E)$.
From here, I think I need to assume that it isn't a minimum vertex cover and then prove that it is by contradiction, but I'm having trouble with that. Am I on the right path? Any hints?
Best Answer
Let $I$ be a maximal independent set. Then, for $e\in E(G)$, $e$ has at least one vertex not in $I$. Hence $V(G)\setminus I$ is a vertex cover. Suppose $V(G)\setminus I$ is not a minimal vertex cover, then there is $v\in V(G)\setminus I$ such that $(V(G)\setminus I) - v$ is a vertex cover. This means that all vertices in the neighbourhood $N(v)$ of $v$ are in $V(G)\setminus I$, that is, $\{v\}\cup N(v)$ is disjoint with $I$. Hence, $I + v$ is also a independent set, which contradicts the maximality of $I$.