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