A graph G_φ with n triangles can be constructed from a 3-CNF formula φ with n clauses in polynomial time (O(n²) edges from 3n vertices)

The graph \(G_{\phi}\) for the formula \((p_1 \vee p_2 \vee p_3) \wedge (\neg p_1 \vee p_2 \vee \neg p_3) \wedge (p_1 \vee \neg p_2 \vee \neg p_3)\). A reduction of \(3\text{-}\sc{SAT}\) to \(\sc{INDEPENDENT}\ \sc{SET}\) can now be described as follows: Let \(\phi\) be a \(3\text{-}\sc{CNF}\) formula consisting of \(n\) clauses as depicted above. We construct a graph \(G_{\phi} = \langle V,E \rangle\) consisting of \(n\)-triangles \(T_1,\ldots,T_n\) such that the nodes of \(T_i\) are respect