Vertex Cover Proof I am working on an exercise describe like so:
Without using knowledge about cliques, prove that a graph G has an independent set of size k if and only if G has a vertex cover of size n - k where n is the size of V, the vertex set of G.
I am attempting to write a proof for this and was hoping for help with the concept and wording.
By definition of independent sets, the complement of independent set of size k will result in every vertex being connected by an edge to form a maximum clique size of n - k.
Is this sufficient enough or how should I add to it to make it concrete?
 A: Let $I$ be an independent set of size $k$ in $G$. The set $V(G) \setminus I$ is a vertex cover of the desired size. It covers every edge in the graph because there can be no edges between vertices of $I$. In other words, every edge of $G$ has some endpoint lying in $V(G) \setminus I$, and these are precisely the vertices in the proposed cover.
A: I saw a similar question to this one in $2^{nd}$ part of:  Question asking relation between vertex cover and independent set. My answer to that question might be a simpler argument using the definitions given in that question: 
Since a vertex cover $C$ includes at least one end point of each edge, $V(G)−C$ must include either none of the endpoints of one edge or 1 of them. So it is an independent set by definition. Assuming $|V(G)| = n$, if $G$ has an independent set of size $k$, then we can find a vertex cover of size $n-k$. And same argument also holds for converse, that is, if $G$ has a vertex cover of size $n-k$, we can find an independent set of size $k$.
This may not be a different approach but I thought it can be helpful with the definitions given and supporting the argument here by using the argument asked in Question asking relation between vertex cover and independent set.
