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? 
 A: 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$.
A: 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.
