Clique & Vertex Cover

Clique ${\le }_p$ Vertex Cover

$G$ has a clique of size $k$ $⟺$ $\bar{G}$ has a vertex cover of size $|V|-k$

$(\Rightarrow )$:

For all edge in $\bar{G}$, at least one end point is not in the clique, so edges are covered by those vertexes that are not in the clique, which has size $|V|-k$.

$(\Leftarrow )$:

Consider those edges that are currently not present in $G$, then their endpoint must be in vertex cover in $\bar{G}$, since the vertexes in clique are all connected. Consider the contrapositive of this argument, that means, if both endpoints are not in vertex cover, then there must be a edge connecting them, which forms a clique of size of $|k|$.

Links

• NP Completeness Definition
• 3-SAT & Clique

Reference

• Introduction to Algorithm