Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I want to show that there is a polynomial-time reduction from the standard $\text{Clique}$ problem to the $\text{N-Degree-Clique}$ problem, where: $$ \text{N-Degree-Clique} = \{ \langle G, k\rangle: \text{$G$ has a clique of size $\geq k$,} \\ \text{and every vertex of $G$ has degree at least N} \}$$
I am not sure how to map the last condition and could use help figuring out a reduction.
One almost correct reduction looks like: consider the graph $G'$ that is obtained by adding $N$ new vertices to the input graph $G$. Also, add edges that connect every new vertex to all the vertices in $G$. Its not hard to show that $G$ has a clique of size at least $k$ iff $G'$ has a clique of size at least $k+1$. Note that the degree of each new vertex equals the number of vertices of $G$, which not necessarily at least $N$. But this is a minor issue that I leave for you to fix (along with proving correctness).
