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
    Your sketch seems to me to assume knowledge about cliques.2011-09-05
  • 0
    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.2011-09-05
  • 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
    Hi Austin, I am unfamiliar with the forward slash notation V(G) \ I. Can you please elaborate on this? Thanks.2011-09-05
  • 0
    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.2011-09-05
  • 0
    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?2011-09-05
  • 0
    The construction I gave gives *a* vertex cover, but it is not always going to be the minimum. If you read at http://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.2011-09-05
  • 0
    @raphnguyen My pleasure. We seem to be browsing SE at precisely the same time every day.2011-09-06
  • 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.