Now define a mapping from instances of \(3\text{-}\sc{SAT}\) to instances of \(\sc{INDEPENDENT}\ \sc{SET}\) as \(f(\phi) = \langle G_{\phi},n \rangle\). As \(G_\phi\) contains \(3n\) vertices (and hence at most \(O(n^2)\) edges), it is evident that \(f(x)\) can be computed in polynomial time. To see that \(f(\phi)\) is a reduction of \(3\text{-}\sc{SAT}\) to \(\sc{INDEPENDENT}\ \sc{SET}\), first suppose that \(v\) is a valuation such that \(\llbracket \phi \rrbracket_v = 1\).  Then we must have \(\llbracket \ell^i_j \rrbracket_v = 1\) for at least one literal in every clause of \(\phi\). Picking the nodes corresponding to this literal in each triangle \(T_i\) in \(\phi\) thus yields an independent set of size \(n\) in \(G_{\phi}\). Conversely, suppose that \(V' \subseteq V\) is an independent set of size \(n\) in \(G_{\phi}\). By construction, \(V'\) contains exactly one vertex in each of the \(T_i\). And since there is an edge between each pair of nodes labeled with oppositely signed literals in different triangles in \(G_{\phi}\), \(V'\) cannot contain any contradictory literals. A satisfying valuation \(v\) for \(\phi\) can be constructed by setting \(v(p_i) = 1\) if a node labeled with \(p_i\) appears in \(V'\) and \(v(p_i) = 0\) otherwise.