Maximal Independent Set and Minimal Vertex Cover.

Question

Maximal Independent Set and Minimal Vertex Cover. I can have multiple maximal independent sets for a graph.. Now for a particular Maximal independent set , if I remove the vertices contained in it from total vertices in a graph...then my question is am I sure to get a minimal vertex cover...? Like say if the vertices of a graph are "abcde" and say if "abc" is a maximal independent set then can I say for sure that "de" is a minimal vertex cover...?

Plz correct me if I have done something totally wrong or is the claim given wrong...by seeing this.

Answer 1

Let $G=(V,E)$ be undirected graph, and $G^c$ is complement, where $G^c=(V,V\times V \setminus E)$

$S\subseteq V(G)$ is maximal independent set in $G$ $\iff$ $S$ is maxiaml clique in $G^c$.

---

As for a vertex cover:

$S\subseteq V(G)$ is a maximal independent set in $G\iff V\setminus S$ is a set cover in $G$

Proof of $\leftarrow$ direction:

Let $A\subseteq V(G)$ be some vertex cover in $G=(V,E)$.

Prop : $\forall u,v\in V(G)\setminus A \ \ (u,v)\notin E(G)$

proof: Otherwise $A$ won't be a vertex cover.

Answer 2

Yes, they will be a minimal vertex cover.

First, the fact that $S$ is an independent set (not necessary maximal) means that no edge lies within $S$, so every edge meets $V\setminus S$, meaning that $V\setminus S$ is a vertex cover.

Secondly, the fact that $S$ is a maximal independent set means that for every vertex $v\in V\setminus S$, adding $v$ to $S$ does not give an independent set. Thus there is an edge meeting $v$ and some vertex in $S$. If we removed $v$ from $V\setminus S$, this edge wouldn't be covered, so we would no longer have a vertex cover. This is true for every $v\in V\setminus S$, so $V\setminus S$ is minimal.