Given $G=(V,E)$, undirected graph, a group of vertices $S$ is called almost clique if by adding a single edge, $S$ becomes a clique.
Consider the language: $L=\{\langle G,t\rangle \mid \text{the graph \(G\) contains a \(t\)-sized almost-clique}\}$. Prove that $L$ is NP-complete.
Obviously, it is solved by polynomial reduction, but is it from Clique or 3SAT? And how?
You can reduce to this from $CLIQUE$.
Given a graph $G=(V,E)$ and $t$, construct a new graph $G^*$ by adding two new vertices $\{v_{n+1},v_{n +2}\}$ and connecting them with all of $G$'s vertices but removing the edge $\{v_{n+1},v_{n+2}\}$, i.e. they are not neighbors in $G^*$. return $G^*$ and $t+2$.
If $G$ has a $t$ sized clique by adding it to the two vertices we get an $t+2$ almost clique in $G^*$ (by adding $\{v_{n+1},v_{n+2}\}$).
If $G^*$ has a $t+2$ almost clique we can look at three cases:
1) It contains the two vertices $\{v_{n+1},v_{n+2}\}$, then the missing edge must be $\{v_{n+1},v_{n+2}\}$ and this implies that the other $t$ vertices form a $t$ clique in $G$.
2) It contains one of the vertices $\{v_{n+1},v_{n+2}\}$, say w.l.o.g. $v_{n+1}$, then the missing edge must be inside $G$, say $e=\{u,v\}\in G$. If we remove $u$ and $v_{n+1}$ then the other $t$ vertices, which are in $G$ must form a clique of size $t$.
3) It does not contain any of the vertices $\{v_{n+1},v_{n+2}\}$, then it is clear that this group is in $G$ and must contain a clique of size $t$.
It is also clear that the reduction is in polynomial time, actually in linear time, log-space.
The subgraph $S$ of $G=(V,E)$ is a called an $s$-defective clique when $E(G[S]) \geq \binom{|S|}{2} - s$, i.e., missing at most $s$ edges from clique. Your definition is similar to 1-defective clique.
The question about hardness can be done in one line. Observe, that defective clique is a hereditary structure. By Yannakakis theorem its optimization maximum problem is NP-hard.
