Does the way a graph $G$ is encoded affect the proof that $CLIQUE$ is in $NP$? For a proof that $CLIQUE = \{ \langle G, k \rangle | G$ is an undirected graph with a $k$-clique. $\}$ is in $NP$ by constructing a nondeterministic Turing machine $N$, where
$N$ = $``$On input $\langle G, k \rangle$:


*

*Nondeterministically select a subset $c$ of $k$ nodes of $G$.

*Test whether $G$ contains all edges connecting nodes in $c$.

*If yes, $accept$; otherwise, $reject."$
Does the way we encode $G$ affect this proof?
Are encoding $G$ with adjacency matrix and encoding $G$ by first listing the number of vertices (in binary) and listing all edges (in binary), for example, ($11_2; (01_2, 10_2), (01_2, 11_2), (10_2, 11_2)$) represents a triangle, all valid for this proof?
Does this proof make any implicit assumption on encoding $G$?

How $G$ is encoded makes a big difference.  Consider these two (fairly extreme) cases:


*

*We encode $G$ as the union of max-cliques.  Then even a deterministic Turing machine can solve the CLIQUE problem in polynomial time with this encoding.

*We encode $G$ as an adjacency matrix, but instead of writing the bit in cell $(i,j)$ once, we write it $2^{i+j}$ times.  It would take exponential time just to read the input.  So a non-deterministic Turing machine cannot solve CLIQUE in (worst case) polynomial time with this encoding.
By default, we assume a "useful" encoding e.g.: (a) edge list, (b) adjacency matrix, or (c) list of neighbours.  There will be a polynomial-time algorithm to convert between any two of these, so which one of these encodings we choose will not affect membership in NP.
