# What is the relationship between Clique, Independent Set, and Vertex Cover?

I'm aware that Vertex Cover and Independent Set are complements of eachother, but I've also heard Independent Set referred to something in relation to Clique; I just don't recall what. It can't be the complement, because if it is, then Clique and Vertex cover would be the same, wouldn't it?

-

A set of vertices in a graph $\Gamma$ form a clique iff they form an independent set in the complement of $\Gamma$. Is that what you were looking for?

In response to your comment below: Cliques and independent sets are sets of vertices rather than graphs, so they technically can't be complementary graphs. However, the induced subgraph spanned by a clique is the complement of the induced subgraph spanned by an independent set of the same size.

-
That seems to make sense... I heard from my prof something about complementary graphs, but I didn't understand how... clique and independent set are not directly complementary graphs of eachother, but the same set of vertices mean two different things based on the complement of the bigger graph.. –  agent154 Feb 20 '13 at 20:09
[I'm not actually sure if 'spanned by' is correct terminology there. Could someone please correct me if I'm wrong?] –  Tara B Feb 20 '13 at 23:38
I recently had a refresher on graph terminology, and I think spanned is right. A spanning subgraph G' of G is one that has all the same vertices as G, but not necessarily all the same edges... –  agent154 Mar 10 '13 at 0:05