Clique, independent set, and vertex cover decision problems

Let $G=(V,E)$ be a finite simple graph.

• A subset $K\subseteq V$ is a clique when every two distinct vertices of $K$ are adjacent.
• A subset $I\subseteq V$ is an independent set when no two distinct vertices of $I$ are adjacent.
• A subset $C\subseteq V$ is a vertex cover when every edge in $E$ has at least one endpoint in $C$.

The associated decision problems are:

• CLIQUE: given $(G,k)$ with $k\in \mathbb{N}$, decide whether $G$ has a clique of size at least $k$;
• INDEPENDENT SET: given $(G,k)$, decide whether $G$ has an independent set of size at least $k$;
• VERTEX COVER: given $(G,k)$, decide whether $G$ has a vertex cover of size at most $k$.

Because the input graph is simple, adjacency means the edge relation from Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree on the vertex set of A finite simple graph is a finite vertex set together with a set of two-element vertex subsets.