Are all subsets of NP-complete languages also NP-complete? Is the following assertion true or false?


  If the language $L$ is NP-complete and $Q ⊆ L$, then $Q$ is NP-complete.


I know for example that $k$-coloring is NP-complete if I take $k$ as input, but 2-coloring is an infinite subset of this which is in P (see link). Therefore, for me, the assertion is false. However, I'm working through languages, and I cannot figure out an example (with language) useful to show false the assertion.
Take any infinite NP-complete language $L$. The language $L$ has uncountably many subsets, and particular there is some uncomputable subset $Q \subseteq L$. Since $Q$ is uncomputable, in particular it is not in NP, and so not NP-complete.

You can also try your example. Let $L$ consist of all pairs $(G,k)$ such that $G$ can be colored using at most $k$ colors, and let $Q$ consist of all pairs $(G,2)$ such that $G$ is bipartite; note that $Q \subseteq L$. It is known that $L$ is NP-complete, whereas $Q$ is in P. Therefore $Q$ is not NP-complete unless P=NP.