1. **Problem Statement:** We want to construct a CNF Boolean expression $\phi_H$ for graph $H$ such that $\phi_H$ is True if and only if the assignment of truth values to variables $v_i$ represents a triangle-free vertex cover of $H$. 2. **Definitions:** - A vertex cover $X$ of graph $G$ is a set of vertices such that every edge in $E(G)$ has at least one endpoint in $X$. - A triangle in $G$ is a set of three vertices all pairwise adjacent. - A triangle-free vertex cover is a vertex cover containing no triangles. 3. **Variables:** - For each vertex $i \in V(H)$, define a Boolean variable $v_i$ which is True if vertex $i$ is in the vertex cover. 4. **Encoding vertex cover condition:** - For every edge $(i,j) \in E(H)$, at least one of $v_i$ or $v_j$ must be True. - This is encoded as a clause: $$ (v_i \lor v_j) $$ 5. **Encoding triangle-free condition:** - For every triangle $(i,j,k)$ in $H$, the set $\{v_i, v_j, v_k\}$ cannot all be True simultaneously. - This means at least one of $v_i, v_j, v_k$ is False. - Encode as: $$ (\neg v_i \lor \neg v_j) \land (\neg v_j \lor \neg v_k) \land (\neg v_i \lor \neg v_k) $$ - This forbids all three vertices in the triangle being in the cover. 6. **Apply to graph $H$:** - Vertices: $\{1,2,3,4,5,6,7\}$ - Edges: $(1,4), (1,3), (1,2), (3,5), (5,7), (2,6), (7,6)$ - Triangles in $H$: - Check triples: The only triangle is $\{1,2,3\}$ because edges $(1,2), (2,3), (1,3)$ exist. 7. **Construct $\phi_H$:** - Vertex cover clauses: $$ (v_1 \lor v_4) \land (v_1 \lor v_3) \land (v_1 \lor v_2) \land (v_3 \lor v_5) \land (v_5 \lor v_7) \land (v_2 \lor v_6) \land (v_7 \lor v_6) $$ - Triangle-free clauses for triangle $\{1,2,3\}$: $$ (\neg v_1 \lor \neg v_2) \land (\neg v_2 \lor \neg v_3) \land (\neg v_1 \lor \neg v_3) $$ 8. **Final CNF expression:** $$ \phi_H = (v_1 \lor v_4) \land (v_1 \lor v_3) \land (v_1 \lor v_2) \land (v_3 \lor v_5) \land (v_5 \lor v_7) \land (v_2 \lor v_6) \land (v_7 \lor v_6) \land (\neg v_1 \lor \neg v_2) \land (\neg v_2 \lor \neg v_3) \land (\neg v_1 \lor \neg v_3) $$ 9. **Summary:** - The CNF $\phi_H$ encodes the vertex cover condition for all edges and forbids any triangle from being fully included in the cover. - This method generalizes to any graph by: - Adding clauses for each edge to ensure coverage. - Adding clauses for each triangle to forbid all three vertices simultaneously. This completes the construction of the CNF Boolean expression $\phi_H$ for the triangle-free vertex cover of graph $H$.