[proofplan]
We construct a many-one reduction by sending a graph to its complement while preserving the parameter $k$. Independent sets in a graph are exactly cliques in its complement, so the construction preserves yes-instances and no-instances. To make the reduction a total function on strings, malformed encodings are sent to one fixed no-instance of $\textsc{Clique}$. The complement graph can be computed by scanning all unordered pairs of vertices, so the reduction runs in polynomial time.
[/proofplan]
[step:Choose a fixed no-instance of $\textsc{Clique}$ for malformed inputs]
Let $\Sigma$ be the fixed finite alphabet used for graph encodings, and let $\Sigma^*$ denote the set of all finite strings over $\Sigma$. Let $H=(V_H,E_H)$ be the finite simple undirected graph with vertex set $V_H=\{a,b\}$ and edge set $E_H=\varnothing$. Then $\langle H,2\rangle \notin \textsc{Clique}$, because the only subset of $V_H$ of cardinality $2$ is $\{a,b\}$, and its two distinct vertices are not adjacent in $H$.
This no-instance will be the output on every string that is not a well-formed encoding of an $\textsc{Independent-Set}$ instance.
[/step]
[step:Define the complement-graph transformation on well-formed inputs]
For a well-formed input string $w=\langle G,k\rangle$, let $G=(V,E)$ be the encoded finite simple undirected graph and let $k \in \mathbb{N}$ be the encoded integer. Define the complement graph $\overline{G}=(V,\overline{E})$ by
\begin{align*}
\overline{E}=\{\{u,v\}\subset V : u\neq v \text{ and } \{u,v\}\notin E\}.
\end{align*}
Define the total map
\begin{align*}
F:\Sigma^*\to\Sigma^*, \quad F(w)=\langle \overline{G},k\rangle \text{ if } w=\langle G,k\rangle \text{ is well formed, and } F(w)=\langle H,2\rangle \text{ otherwise}.
\end{align*}
The map $F$ is well-defined on all strings because each input string is either a well-formed encoding $\langle G,k\rangle$ or is not.
[/step]
[step:Verify that independent sets become cliques in the complement]
Let $w\in\Sigma^*$ be a well-formed input with $w=\langle G,k\rangle$, where $G=(V,E)$ is a finite simple undirected graph and $k\in\mathbb{N}$. Let $S\subset V$ be any subset. By definition, $S$ is independent in $G$ iff for every pair of distinct vertices $u,v\in S$, the unordered pair $\{u,v\}$ is not an element of $E$. By the definition of $\overline{E}$, this is equivalent to saying that for every pair of distinct vertices $u,v\in S$, the unordered pair $\{u,v\}$ is an element of $\overline{E}$. This is exactly the assertion that $S$ is a clique in $\overline{G}$.
Therefore $G$ has an independent set of cardinality at least $k$ iff $\overline{G}$ has a clique of cardinality at least $k$.
[guided]
Fix a well-formed input $w=\langle G,k\rangle$, where $G=(V,E)$ is a finite simple undirected graph and $k\in\mathbb{N}$. We need to prove that the output $\langle \overline{G},k\rangle$ has the same yes-or-no answer for $\textsc{Clique}$ as the input has for $\textsc{Independent-Set}$.
Let $S\subset V$ be an arbitrary subset. The set $S$ is independent in $G$ precisely when no two distinct vertices in $S$ are adjacent in $G$. Written in the edge-set notation, this says:
\begin{align*}
\text{$S$ is independent in $G$} \iff \text{for all distinct } u,v\in S,\ \{u,v\}\notin E.
\end{align*}
Now use the definition of the complement graph. The graph $\overline{G}=(V,\overline{E})$ has the same vertex set as $G$, and an unordered pair $\{u,v\}$ with $u\neq v$ is an edge of $\overline{G}$ exactly when it is not an edge of $G$. Thus, for distinct $u,v\in V$,
\begin{align*}
\{u,v\}\notin E \iff \{u,v\}\in \overline{E}.
\end{align*}
Substituting this equivalence into the condition for independence gives
\begin{align*}
\text{$S$ is independent in $G$} \iff \text{for all distinct } u,v\in S,\ \{u,v\}\in \overline{E}.
\end{align*}
The right-hand condition is exactly the definition that $S$ is a clique in $\overline{G}$. Since the same subset $S$ is being used in both graphs, its cardinality is unchanged. Hence there exists an independent set $S\subset V$ with $|S|\ge k$ in $G$ iff there exists a clique $S\subset V$ with $|S|\ge k$ in $\overline{G}$.
[/guided]
[/step]
[step:Check malformed inputs and conclude correctness of the reduction]
Let $w\in\Sigma^*$. If $w$ is not a well-formed encoding of an $\textsc{Independent-Set}$ instance, then $w\notin\textsc{Independent-Set}$ by definition of the language of the decision problem. In this case $F(w)=\langle H,2\rangle$, and the first step showed $\langle H,2\rangle\notin\textsc{Clique}$.
If $w$ is well formed, write $w=\langle G,k\rangle$. The previous step gives
\begin{align*}
w\in\textsc{Independent-Set} \iff F(w)=\langle \overline{G},k\rangle\in\textsc{Clique}.
\end{align*}
Combining the malformed and well-formed cases, for every string $w\in\Sigma^*$,
\begin{align*}
w\in\textsc{Independent-Set} \iff F(w)\in\textsc{Clique}.
\end{align*}
[/step]
[step:Show that the transformation is computable in polynomial time]
For a well-formed encoding $\langle G,k\rangle$ with $G=(V,E)$, an algorithm computes $\overline{G}$ by scanning every unordered pair $\{u,v\}\subset V$ with $u\neq v$ and writing $\{u,v\}$ to $\overline{E}$ exactly when $\{u,v\}\notin E$. If $n=|V|$, then the number of unordered pairs is
\begin{align*}
\frac{n(n-1)}{2}.
\end{align*}
Thus the number of pair checks is polynomial in $n$, and hence polynomial in the length of the graph encoding. The preliminary well-formedness check and the copying of $k$ are also polynomial-time operations in the input length.
Therefore $F:\Sigma^*\to\Sigma^*$ is a polynomial-time computable function satisfying
\begin{align*}
w\in\textsc{Independent-Set} \iff F(w)\in\textsc{Clique}
\end{align*}
for every $w\in\Sigma^*$. Hence $\textsc{Independent-Set}\le_p\textsc{Clique}$.
[/step]
