2
$\begingroup$

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?

$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$
    – walkar
    Commented Apr 26, 2016 at 2:52
  • $\begingroup$ 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 :) $\endgroup$ Commented Apr 26, 2016 at 2:54
  • $\begingroup$ $\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. $\endgroup$
    – walkar
    Commented Apr 26, 2016 at 3:00
  • $\begingroup$ Oh! I didn't realize that this used $\LaTeX$ :) That's good to know! $\endgroup$ Commented Apr 26, 2016 at 3:10

2 Answers 2

5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Shreck Ye
    Commented Oct 9, 2019 at 11:11
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .