# Relationship between Maximal Independent Set and Minimum Vertex Cover

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?

• Be careful, minimal is not necessarily minimum. A minimal vertex cover is one such that no proper subset is also a vertex cover. The minimum vertex cover is the minimum cover of smallest cardinality. Commented Apr 26, 2016 at 2:52
• Thank you, I corrected the question to make sure it reflected that I meant minimal not minimum. Also thank you for the formatting edit, I'm now to the math stack exchange and have no clue how to format things yet :) Commented Apr 26, 2016 at 2:54
• $\LaTeX$ is pretty standard in mathematics. I highly suggest learning it. There are a lot of resources to learn out -- Google and TeX SE are super useful. Commented Apr 26, 2016 at 3:00
• Oh! I didn't realize that this used $\LaTeX$ :) That's good to know! Commented Apr 26, 2016 at 3:10

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

• Why does $V(G) \setminus I$ being not a minimal vertex cover imply that $\exists v \in V(G) \setminus I$, s.t. $(V(G) \setminus I - v)$ is a vertex cover? I think it only means that there is a smaller vertex cover, and doesn't necessarily imply that you can deduct a vertex from $V(G) \setminus I$ to get a smaller vertex cover. Commented Oct 9, 2019 at 11:11

Here is alternative proof, correct me if i'm wrong.

first

• $$\alpha(G):=$$ size of maximum independent set.
• $$\tau(G):=$$ size of minimum vertex cover.
• $$v(G):=$$ number of vertices in G.

we prove that:

• $$\tau(G) + \alpha(G) = v(G)$$

with shows that yes if you start with a minimum vertex cover and take all the vertices it doesn't take you will be left with a maximum independent set, and vise versa.

i.e the size of the maximum vertex cover is $$v(G)-\alpha(G)$$, and vise versa.

#### proof $$\alpha(G)\geq v(G)-\tau(G)$$ :

Assume $$S$$ is a maximum vertex cover in G. then look at $$S':=V(G)-S$$, we first prove $$S'$$ is independent set.

Assume $$S'$$ is not independent set, i.e there exist $$u,v\in S'$$, such that $$uv\in E(G)$$, with implies that $$u,v\notin S$$, then $$S$$ doesn't cover the edge $$uv$$, contradiction.

Hence from that you have concluded that $$\alpha(G)\geq v(G)-\tau(G)$$.

#### proof : $$\tau(G)\leq v(G)-\alpha(G)$$ :

Similarly, Assume now $$S$$ is a maximum independent set, we then prove that $$S':=V(G)-S$$ is a vertex cover.

Assume by contradiction that it's not. then it holds that there exist $$uv\in E(G)$$ such that $$u\notin S'$$ and $$v\notin S'$$, hence again we conclude that both must be in $$S$$, then we observe that $$S$$ is not an independent set.

we then observe that: $$\tau(G)\leq v(G)-\alpha(G)$$.

move the alpha and tau, and we get that $$\alpha(G)\leq v(G)-\tau(G)$$, and from previous observation we got that $$\alpha(G)\geq v(G)-\tau(G)$$.

hence, it must hold that: $$\tau(G) + \alpha(G) = v(G)$$

now if you assume there is a vertex cover with less vertices, then the equation simply doesn't hold.