# Prove "Vertex Cover OR Clique" is NP complete

Instance: An undirected graph $$G$$ and a positive integer $$k$$

Question: Does $$G$$ contain a vertex cover of size $$\leq k$$ or a clique of size $$\geq k$$?

Obviously, this problem is solved by polynomial reduction, but is it from Clique or Vertex Cover? And how?

I've tried to reduce from both problems, but seem to get stuck. If I reduce from Clique, for example, It seems I'd need to guarantee that there isn't a Vertex Cover, but it's not clear to me how to do that. It seems reducing from Vertex Cover is more promising, but I run into the same issue

First, notice that the clique problem remains NP-hard even if we restrict $$k$$ to lie in $$3 \leq k \leq n$$ (because outside this range the problem is trivially solvable in polynomial time).
Given a graph $$G$$ on $$n$$ vertices and $$3\leq k \leq n$$, construct a graph $$G'$$ by taking the disjoint union of $$G$$ with a perfect matching on $$2(n+1)$$ additional vertices.
Now, $$G$$ has a clique of size $$\geq k$$ if and only if $$G'$$ has a clique of size $$\geq k$$. This is because if we find a clique of size $$\geq k\geq 3$$ in $$G$$ then it cannot lie in the matching part, as this has no cliques of size greater than $$2$$. Moreover, $$G'$$ has no vertex cover of size $$\leq k$$, as you need at least $$n+1$$ vertices to cover the matching. Thus, $$G$$ has a clique of size $$k$$ if and only if $$G'$$ has a clique of size $$\geq k$$ or a vertex cover of size $$\leq k$$ (this second condition always being false).