Hardness of $k$-Plex Definition. Given an undirected graph $G = (V,E)$, a $k$-plex is a subgraph $G'$ of $G$ such that each vertex in $G'$ is connected to at least $s - k$ other vertices in $G'$, where $s$ is the # of vertices in $G'$. 


Computing the maximum $k$-plex is NP-hard since a clique is just a $1$-plex. In my understanding, such a reduction only shows the hardness of computing the maximum $1$-plex. Moreover, when $k=|V|$, the problem becomes trivial because any subgraph of $G$ is a $k$-plex then.


  Question. Is the maximum $2$-plex still NP-hard to be computed? Or more generally, given a graph $G = (V,E)$, what is the maximum $k$ such that the maximum $1$-plex, the maximum $2$-plex, $\cdots$ and the maximum $k$-plex are all NP-hard to be computed?


This question seems interesting but I did not come up with a reduction from any other NP-complete problem, even from the MaxClique.
Lemma. If a graph has a $k$-plex on $m$ vertices, then it has a clique on $\frac m{k+1}$ vertices.

Proof. Greedily pick the vertices of the clique from the $k$-plex.

Since a clique on $m$ vertices is also a $k$-plex on $m$ vertices (for any $k$), we get that the size of the maximum $k$-plex is a $k$-approximation of the size of the maximum clique.
Since clique is hard to approximate with an $O(n^{1-\epsilon})$ factor, determining the largest $k$-plex is also hard for any $k=O(n^{1-\epsilon})$.