# Reduce Clique to Vertex Cover

I read on the internet that it's possible to reduce clique to vertex cover. Almost everyone use this theorem:

if a graph $G$ has a clique of size $k$ then the complement of $G$ has a vertex cover of size $n-k$, where $n$ is the number of vertices.

Consider the graph on five vertices and the following edges: a clique on $\{1,2,3,4\}$ and $(1,5),(2,5),(3,5)$. The complement of this graph has only one edge, and it does not cover the set of vertices.

Is the statement I quoted correct?

• See here, for example: www8.cs.umu.se/kurser/TDBA77/VT06/algorithms/BOOK/BOOK3/…. – Yuval Filmus Jan 23 '15 at 18:43
• So, I can reduce Clique to Indepdent Set and then to Cover Set Problem. Unfortunately, I don't see what is wrong with my above explanation – Yeynno Jan 23 '15 at 18:58
• Work through the reduction and you'll what, if anything, goes wrong. It's best if you did it on your own. – Yuval Filmus Jan 23 '15 at 19:00
• I tried to do this on my own and I failed, because I found counter-example that it doesn't work – Yeynno Jan 23 '15 at 19:03
• A good first step is making sure you understand all the definitions involved. – Yuval Filmus Jan 23 '15 at 19:24

## 1 Answer

You're misunderstanding what Vertex Cover is: the task is to find a set of vertices which "cover" or "touch" all edges. Each of the vertices $4,5$ covers the unique edge $(4,5)$ in the complement of your graph.

The theorem states that the size of the maximum clique in a graph equals the size of a minimum vertex cover in its complement. This is because a set $A$ of vertices is a clique in a graph $G$ if and only if its complement $\overline{A}$ is a vertex cover in the complement graph $\overline{G}$.

Indeed, $A$ is a clique in $G$ if any two $x,y \in A$ are connected in $G$; $\overline{A}$ is a vertex cover in $\overline{G}$ if for every edge $(x,y) \in \overline{G}$, one of $x,y$ is in $\overline{A}$. So $\overline{A}$ is not a vertex cover in $\overline{G}$ if there exists an edge $(x,y) \in \overline{G}$ such that $x,y \notin \overline{A}$, i.e. if for some $x,y \in A$, $(x,y) \notin G$; this is exactly the condition that $A$ is not a clique in $G$.

• Yes, I didn't understand Vertex Cover well. Thank you – Yeynno Jan 23 '15 at 19:19