# Prove that clique cover is NP Complete

I want to use Vertex Cover as a known $$NP$$-complete Problem for the reduction. The claim is that if a have a vertex cover in graph $$G$$ with size $$\le k$$, I will have a clique cover in $$G^\prime$$ with total number of cliques $$\le k$$

I want to reduce vertex cover problem to clique cover problem in the following way:

1. For each edge in $$G$$, I will create a corresponding vertex in $$G^\prime$$. In the picture, each e$$_i$$ in G corresponds to v$$_i$$ in $$G^\prime$$ for $$1\le i\le5$$

2. Two vertices in $$G^\prime$$ will be connected by an edge if their corresponding two edges in G have one vertex in common. For example, there is an edge between v$$_1$$ to v$$_2$$ as their corresponding edges e$$_1$$ and e$$_2$$ have one vertex in common which is a.

3. Each clique in $$G^\prime$$ corresponds to a vertex in G and that vertex belongs to the vertex cover. For example, for the graph in picture I have vertex cover {a,c}. With vertex a, I get a clique {v$$_1$$, v$$_2$$, v$$_5$$} and with vertex c, I get clique {v$$_3$$, v$$_4$$} in $$G\prime$$.

Now I don't know how to prove No instance in opposite direction: If $$G^\prime$$ doesn't have a clique cover with $$\le k$$ cliques (i.e it needs at least $$k+1$$ cliques), $$G$$ doesn't have a vertex cover size which is $$\le k$$.

Can anybody shed some light on this issue?

• Keep trying. Also, try to refute your claim in parallel. Commented Feb 24, 2017 at 3:17

The problem is with your claim "Each clique in $$G'$$ corresponds to a vertex in $$G$$". This is false, because there could be a clique associated to two different vertices.
For example, consider a 3-clique $$G = (\{v_1, v_2, v_3\}, \{v_1v_2, v_2v_3, v_1v_3\})$$. The corresponding graph $$G'$$ is also a 3-clique, but the 3 edges don't have a unique common vertex. In this case, $$G'$$ has a clique cover of size $$1$$, but $$G$$ doesn't.