# 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?

-
Your sketch seems to me to assume knowledge about cliques. –  Henning Makholm Sep 5 '11 at 22:36
If a graph had n vertices and no edges, then would its vertex cover be non-existent? I thought that vertex covers were the minimum set of vertices such that every edge in the graph is attached to at least one vertex in the set. –  raphnguyen Sep 5 '11 at 22:53
@raphnguyen I misunderstood the definition of vertex cover when I wrote that comment (which is why it's now deleted). Please disregard it. –  Austin Mohr Sep 5 '11 at 22:55

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.
It means those vertices of $G$ that do not belong to $I$. It is sometimes called "set difference", since you are starting with the elements of the first set and removing the elements of the second set. –  Austin Mohr Sep 5 '11 at 22:57
The construction I gave gives a vertex cover, but it is not always going to be the minimum. If you read at en.wikipedia.org/wiki/Vertex_cover, you'll see that determining the minimum vertex cover of a graph is NP-Complete (which basically means "very difficult"). An example where $n - k$ is not the minimum, take a triangle and attach a pendant edge to each vertex. This has an independent set of size 3, but the minimum vertex cover is of size 2, not 3, as the proposition we proved gives. –  Austin Mohr Sep 5 '11 at 23:46