Exercise $10\mathrm{.}4\mathrm{.}1$: A $k-$clique in a graph $G$ is a set of $k$ nodes of $G$ such that

there is an edge between every two nodes in the clique. Thus, a $2-$clique is just

a pair of nodes connected by an edge, and a $3-$clique is a triangle. The problem

CLIQUE is: given a graph $G$ and a constant $k,$ does $G$ have a $k-$clique?

a$)$ What is the largest $k$ for which the graph $G$ of Fig. $10\mathrm{.}1$ satisfies CLIQUE?

b$)$ How many edges does a $k-$clique have, as a function of $k?$

c$)$ Prove that CLIQUE is NP$-$complete by reducing the node$-$cover problem

to CLIQUE.