Reduction: Independent Set → Clique

Define complement of graph $G = (V,E)$ to be $\bar{G} = (V, \bar{E})$, where $\bar{E}$ contains those unordered pairs of vertices not in $E$.

CLIQUE ⇒ Finding a complete sub-graph in graph.

A set of nodes $S$ is an independent set of $G$ iff $S$ is a clique of $\bar{G}$ ⇒ nodes have no edges between them in $G$ iff they have all possible edges between them in $\bar{G}$