2
$\begingroup$

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?

  • 0
    @raphnguyen I misunderstood the definition of vertex cover when I wrote that comment (which is why it's now deleted). Please disregard it.2011-09-05

2 Answers 2

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.

  • 0
    My example should say "attach a pendant edge to two of the vertices of the triangle".2011-09-09
0

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.