Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer
    
Hi Austin, I am unfamiliar with the forward slash notation V(G) \ I. Can you please elaborate on this? Thanks. –  raphnguyen Sep 5 '11 at 22:56
    
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
    
Thanks, Austin. So every vertex in I is connected by an edge to at least one vertex in V(G) \ I. Vertices in V(G) \ I would then form the minimum vertex cover. Is there ever an instance where this does not result in the "minimum" vertex cover? –  raphnguyen Sep 5 '11 at 23:04
    
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
    
Thanks again, Austin. –  raphnguyen Sep 6 '11 at 1:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.