where each \(\ell^i_j\) is a literal – i.e. \(\ell^i_j = p_k\) or \(\ell^i_j = \neg p_k\) for some propositional variable \(p_k\). A formula \(\phi\) of this form is satisfiable just in case there exists a valuation satisfying at least one of the literals \(\ell^i_1, \ell^i_2\) or \(\ell^i_3\) for all \(1 \leq i \leq n\). On the other hand, suppose that we consider the family of graphs \(G\) which can be partitioned into \(n \) disjoint triangles in the manner depicted in Figure 3. It is easy to see that any independent set of size \(n\) in such a graph must  contain exactly one vertex from each triangle in \(G\). This in turn suggests the idea of using a graph of this form as a gadget for representing the clauses of a \(3\text{-}\sc{CNF}\) formula.