Given a 3-CNF formula φ with n clauses, a graph G_φ can be constructed consisting of n triangles where each node is labeled with a literal from the corresponding clause

\(\sc{INDEPENDENT}\ \sc{SET}\ \) Given a graph \(G = \langle V,E \rangle\) and a natural number \(k \leq \lvert V\rvert\), does there exist a set of vertices \(V' \subseteq V\) of cardinality \(\geq k\) such that no two vertices in \(V'\) are connected by an edge? \(\sc{VERTEX}\ \sc{COVER}\ \) Given a graph \(G = \langle V,E \rangle\) and a natural number \(k \leq \lvert V\rvert\), does there exist a set of vertices \(V' \subseteq V\) of cardinality \(\leq k\) such that for each edge \(\langle u