[proofplan]
We first show that $\mathrm{INDEPENDENT}\text{-}\mathrm{SET}$ belongs to NP by using the proposed independent set as a certificate and checking all pairs of vertices in polynomial time. For NP-hardness, we reduce from $\mathrm{CLIQUE}$ by sending a graph to its complement while preserving the integer parameter $k$. The key equivalence is that a subset of vertices is a clique in $G$ exactly when it is an independent set in the complement graph $\overline{G}$. Since the complement graph can be constructed by inspecting all unordered pairs of vertices, the reduction is polynomial time, and NP-hardness follows from the NP-completeness of $\mathrm{CLIQUE}$.
[/proofplan]
[step:Verify membership in NP using the proposed independent set as a certificate]
Let $(G,k)$ be an instance of $\mathrm{INDEPENDENT}\text{-}\mathrm{SET}$, where $G=(V,E)$ is a finite simple undirected graph and $k \in \mathbb{N}$. A certificate is a subset $S \subseteq V$, encoded as a list of vertices.
Define the verifier
\begin{align*}
A: \{(G,k,S) : G=(V,E) \text{ is a finite simple undirected graph},\ k \in \mathbb{N},\ S \subseteq V\} \to \{0,1\}
\end{align*}
by setting $A(G,k,S)=1$ exactly when $|S| \geq k$ and, for every distinct $u,v \in S$, the unordered pair $\{u,v\}$ does not belong to $E$.
The verifier first checks that every listed element of $S$ is a vertex of $G$, then checks $|S| \geq k$, and then inspects every unordered pair of distinct vertices in $S$. There are at most $|V|^2$ such ordered inspections and at most $|V|(|V|-1)/2$ unordered pairs, so the verification time is polynomial in the input size of $(G,k)$. Therefore $\mathrm{INDEPENDENT}\text{-}\mathrm{SET} \in \mathrm{NP}$.
[/step]
[step:Define the complement-graph reduction from $\mathrm{CLIQUE}$]
We use the standard NP-completeness of $\mathrm{CLIQUE}$ (citing a result not yet in the wiki: $\mathrm{CLIQUE}$ is NP-complete). The decision problem $\mathrm{CLIQUE}$ has instances $(G,k)$, where $G=(V,E)$ is a finite simple undirected graph and $k \in \mathbb{N}$, and asks whether there is a subset $S \subseteq V$ with $|S| \geq k$ such that every two distinct vertices in $S$ are adjacent in $G$.
For a finite simple undirected graph $G=(V,E)$, define its complement graph $\overline{G}=(V,\overline{E})$ by
\begin{align*}
\overline{E}=\{\{u,v\}: u,v \in V,\ u \neq v,\ \{u,v\} \notin E\}.
\end{align*}
Define the reduction map
\begin{align*}
R: \{(G,k): G \text{ is a finite simple undirected graph and } k \in \mathbb{N}\} \to \{(H,k): H \text{ is a finite simple undirected graph and } k \in \mathbb{N}\}
\end{align*}
by
\begin{align*}
R(G,k)=(\overline{G},k).
\end{align*}
[/step]
[step:Prove that cliques in $G$ are exactly independent sets in $\overline{G}$]
Let $G=(V,E)$ be a finite simple undirected graph, let $k \in \mathbb{N}$, and let $\overline{G}=(V,\overline{E})$ be the complement graph defined above. We prove that
\begin{align*}
(G,k) \in \mathrm{CLIQUE} \iff (\overline{G},k) \in \mathrm{INDEPENDENT}\text{-}\mathrm{SET}.
\end{align*}
Suppose first that $(G,k) \in \mathrm{CLIQUE}$. Then there exists $S \subseteq V$ with $|S| \geq k$ such that, for every distinct $u,v \in S$, one has $\{u,v\} \in E$. By the definition of $\overline{E}$, this implies $\{u,v\} \notin \overline{E}$ for every distinct $u,v \in S$. Hence $S$ is an independent set of size at least $k$ in $\overline{G}$, so $(\overline{G},k) \in \mathrm{INDEPENDENT}\text{-}\mathrm{SET}$.
Conversely, suppose that $(\overline{G},k) \in \mathrm{INDEPENDENT}\text{-}\mathrm{SET}$. Then there exists $S \subseteq V$ with $|S| \geq k$ such that, for every distinct $u,v \in S$, one has $\{u,v\} \notin \overline{E}$. Since $G$ is simple and $\overline{E}$ contains exactly the unordered pairs of distinct vertices not in $E$, it follows that $\{u,v\} \in E$ for every distinct $u,v \in S$. Thus $S$ is a clique of size at least $k$ in $G$, so $(G,k) \in \mathrm{CLIQUE}$.
[guided]
The reduction works because complementing a graph reverses adjacency for distinct vertices. Let $G=(V,E)$ be a finite simple undirected graph, and let $\overline{G}=(V,\overline{E})$ be its complement, where
\begin{align*}
\overline{E}=\{\{u,v\}: u,v \in V,\ u \neq v,\ \{u,v\} \notin E\}.
\end{align*}
We need to prove that the reduction preserves yes-instances and no-instances. Equivalently, we prove
\begin{align*}
(G,k) \in \mathrm{CLIQUE} \iff (\overline{G},k) \in \mathrm{INDEPENDENT}\text{-}\mathrm{SET}.
\end{align*}
First assume that $(G,k)$ is a yes-instance of $\mathrm{CLIQUE}$. By definition, there is a subset $S \subseteq V$ with $|S| \geq k$ such that every two distinct vertices $u,v \in S$ satisfy $\{u,v\} \in E$. The complement graph puts an edge between two distinct vertices exactly when that edge was absent from $G$. Therefore, for every distinct $u,v \in S$, the fact that $\{u,v\} \in E$ implies $\{u,v\} \notin \overline{E}$. This is precisely the condition that no two distinct vertices of $S$ are adjacent in $\overline{G}$. Hence $S$ is an independent set of size at least $k$ in $\overline{G}$.
Now assume that $(\overline{G},k)$ is a yes-instance of $\mathrm{INDEPENDENT}\text{-}\mathrm{SET}$. Then there is a subset $S \subseteq V$ with $|S| \geq k$ such that no two distinct vertices of $S$ are adjacent in $\overline{G}$. In symbols, for every distinct $u,v \in S$, one has $\{u,v\} \notin \overline{E}$. Since $\overline{E}$ contains exactly the unordered pairs of distinct vertices that are not edges of $G$, the statement $\{u,v\} \notin \overline{E}$ forces $\{u,v\} \in E$. Thus every pair of distinct vertices in $S$ is adjacent in $G$, so $S$ is a clique of size at least $k$ in $G$.
This proves that a subset witnesses a clique in $G$ exactly when the same subset witnesses an independent set in $\overline{G}$.
[/guided]
[/step]
[step:Check that the reduction is polynomial time]
Let $n=|V|$ denote the number of vertices of $G=(V,E)$. To construct $\overline{G}$, the algorithm keeps the same vertex set $V$ and inspects each unordered pair $\{u,v\}$ of distinct vertices. There are
\begin{align*}
\frac{n(n-1)}{2}
\end{align*}
such pairs. For each pair, it decides whether $\{u,v\} \in E$ and inserts $\{u,v\}$ into $\overline{E}$ exactly when $\{u,v\} \notin E$. With any standard adjacency-matrix or sorted adjacency-list encoding, this construction takes time polynomial in the size of the encoding of $G$. The integer parameter $k$ is copied unchanged, so the full map $R(G,k)=(\overline{G},k)$ is computable in polynomial time.
[/step]
[step:Conclude NP-completeness]
The previous steps show that $\mathrm{INDEPENDENT}\text{-}\mathrm{SET} \in \mathrm{NP}$ and that $\mathrm{CLIQUE} \leq_p \mathrm{INDEPENDENT}\text{-}\mathrm{SET}$ via the polynomial-time many-one reduction $R(G,k)=(\overline{G},k)$. Since $\mathrm{CLIQUE}$ is NP-complete, every language in $\mathrm{NP}$ many-one reduces in polynomial time to $\mathrm{CLIQUE}$, and composition with $R$ gives a polynomial-time many-one reduction to $\mathrm{INDEPENDENT}\text{-}\mathrm{SET}$. Therefore $\mathrm{INDEPENDENT}\text{-}\mathrm{SET}$ is NP-hard. Together with membership in $\mathrm{NP}$, this proves that $\mathrm{INDEPENDENT}\text{-}\mathrm{SET}$ is NP-complete.
[/step]
