Visual walkthrough — NP-complete problems — 3-SAT, Vertex Cover, Clique, Hamiltonian Path, TSP, Subset Sum

---

Step 1 — The two characters, drawn side by side

WHAT. Two puzzles sit on the table. On the left, a logic puzzle. On the right, a graph puzzle. We will build a bridge between them.

Let me define every word before using it.

WHY. We want to prove Clique is at least as hard as 3-SAT. The tool for "at least as hard" is a reduction (see Polynomial-time Reductions): a fast translator $f$ turning any 3-SAT formula into a graph so that

$\underset{\text{logic answer}}{\underbrace{\phi \text{ is satisfiable}}}⟺\underset{\text{graph answer}}{\underbrace{f(\phi )\text{ has a clique of size }m}}.$

Here $\phi$ (Greek "phi") is our formula and $m$ is its number of clauses. The double arrow $⟺$ means "yes on the left exactly when yes on the right" — the two puzzles always give the same answer.

PICTURE. The logic puzzle and the graph puzzle facing each other, with the translator arrow between.

---

Step 2 — One dot per literal-in-a-clause

WHAT. Take the formula and make one vertex for every literal occurrence. Not one per variable — one per slot in a clause.

Our running example (2 clauses, so $m=2$):

$\phi =\underset{\text{clause }{C}_1}{\underbrace{(x\vee y\vee \neg z)}}\wedge \underset{\text{clause }{C}_2}{\underbrace{(\neg x\vee y\vee z)}}.$

• $C_1$ gives three dots: $x_1,y_1,\neg z_1$. (The subscript $1$ = "lives in clause 1".)
• $C_2$ gives three dots: $\neg x_2,y_2,z_2$.

So $3m=3\times 2=6$ vertices, arranged in $m$ triangles of choice — one triple per clause.

WHY. Each clause needs one true literal to be happy. A vertex will mean "I nominate this literal to be the true one for its clause." Grouping by clause keeps the promise one nominee per clause visible.

WHY no edges inside a triple. We deliberately draw no edge between the three dots of the same clause. A clique can never take two vertices from one clause, so a clique is forced to pick at most one nominee per clause — exactly the rule we want.

PICTURE. Two clause-groups, three dots each, no internal lines.

---

Step 3 — The edge rule: connect the compatible nominations

WHAT. Draw an edge between two dots $u$ and $v$ iff both conditions hold:

$\text{edge}(u,v)⟺\underset{\text{different clauses}}{\underbrace{(\text{clause}(u)\ne \text{clause}(v))}}\text{AND}\underset{\text{not contradictory}}{\underbrace{(u,v\text{ are not }x/\neg x)}}.$

Reading the two guards:

• different clauses — we never link inside one triple (Step 2's rule restated).
• not contradictory — never link $x_i$ to $\neg x_j$. You cannot set $x$ true and $\neg x$ true at the same time, so those two nominations must never appear together.

For our example, listing every cross-clause pair, the only forbidden ones are $x_1$–$\neg x_2$ (that is $x$ vs $\neg x$) and $\neg z_1$–$z_2$ (that is $\neg z$ vs $z$). Every other cross pair gets an edge. So out of the $3\times 3=9$ cross-clause pairs, exactly $2$ are blocked and $7$ are drawn.

WHY. An edge says "these two nominations can coexist." A clique is a set of mutually-coexisting nominations — precisely a consistent set of true literals, one per clause.

PICTURE. Same 6 dots, now with the good edges drawn (chalk-blue) and the two blocked pairs $x_1$–$\neg x_2$ and $\neg z_1$–$z_2$ shown as red dashed "no edges."

---

Step 4 — Set the target size to $k=m$

WHAT. We ask for a clique of size

$k=m=2.$

WHY exactly $m$, not more or less. A clique cannot exceed $m$ because it may use at most one vertex per clause (no intra-clause edges), and there are $m$ clauses. So $m$ is the biggest a clique could possibly be. Asking for a clique of full size $m$ therefore means: hit every clause exactly once — every clause gets a nominee. That is the graph-language for satisfy the whole formula.

PICTURE. A "ceiling meter": max possible clique = number of clauses; we want to touch the ceiling.

---

Step 5 — Forward direction: satisfied formula ⇒ clique of size $m$

WHAT. Suppose the switches are set so $\phi$ is satisfied. In each clause pick one literal that came out true — call it that clause's winner. Take the $m$ winner-vertices.

WHY they form a clique. Take any two winners $u$ (from $C_i$) and $v$ (from $C_j$):

• They are in different clauses ($i\ne j$), so guard 1 passes.
• Both are true under the same assignment, so they cannot be $x$ and $\neg x$ (those can't both be true) — guard 2 passes.

Both guards pass for every pair ⇒ all pairs are adjacent ⇒ the $m$ winners form a clique of size $m$. ✔

PICTURE. Assignment $y=\text{true}$ lights $y_1$ and $y_2$; the edge between them thickens into a size-2 clique.

---

Step 6 — Backward direction: clique of size $m$ ⇒ satisfying assignment

WHAT. Now suppose the graph has a clique $K$ of size $m$. Read it back as logic: for each vertex in $K$, set its literal true.

WHY it's one per clause. $|K|=m$ and no two clique vertices share a clause (no intra-clause edges), so $K$ uses exactly one vertex from each clause. Every clause thus gets a literal we made true ⇒ every clause is satisfied.

WHY it's consistent. Could we accidentally command $x=\text{true}$ and $x=\text{false}$? That would need both $x_i$ and $\neg x_j$ in $K$ — but guard 2 forbids an edge between them, so they can't both be in a clique. No contradiction ever arises; leftover variables can be set arbitrarily. ✔

Steps 5 and 6 together give both directions of the $⟺$, so the reduction is correct.

PICTURE. A clique highlighted in the graph, an arrow "read off" turning it into a truth table, all clauses ticked green.

---

Step 7 — Edge & degenerate cases (never leave a gap)

WHAT & WHY, case by case:

• A clause with a repeated literal, e.g. $(x\vee x\vee y)$. Still three vertices (one per slot); the two $x$ dots simply behave identically. No edge between them (same clause) — harmless.
• Two clauses sharing a literal, e.g. both contain $y$: vertices $y_i$ and $y_j$ do get an edge (different clauses, not opposites), correctly allowing $y=\text{true}$ to serve both.
• A variable appearing only positively (or only negatively). Then no $x/\neg x$ pair exists to block — fewer forbidden edges, never a problem.
• The empty formula ($m=0$). Zero clauses ⇒ zero vertices ⇒ we ask for a clique of size $0$, which trivially exists ⇒ matches "the empty formula is vacuously satisfiable." ✔
• An unsatisfiable formula, e.g. clauses forcing $x$ and $\neg x$ both true across all choices. Then every size-$m$ selection contains a contradictory pair with no edge between them ⇒ no clique of size $m$ ⇒ graph says "no," matching logic's "no." ✔
• Is the translation fast? We list $3m$ vertices and check each of the $\left(\genfrac{}{}{0ex}{}{3m}{2}\right)$ pairs once — that is $O(m^2)$ work, comfortably polynomial. This is what makes it a polynomial-time reduction (see Polynomial-time Reductions).

PICTURE. A 2×2 chalkboard grid: repeated literal, shared literal, empty formula, unsatisfiable core — each with a tick or cross.

---

The one-picture summary

Recall Feynman retelling — say it like a story

We had a logic puzzle: pick a true literal in each clause without ever picking both $x$ and $\neg x$. I turned every literal-slot into a dot, then drew a line between two dots only if they belong to different clauses and aren't opposites — that line means "these two picks can live together." A group where everyone is connected to everyone (a clique) is just a set of picks that all agree and cover every clause. Asking for a clique as big as the number of clauses is asking to make every clause happy at once. So: big clique found = formula satisfiable; no big clique = unsatisfiable. Same puzzle, different costume — and the translation only took $O(m^2)$ time, so any fast Clique-solver would instantly solve 3-SAT. That's why Clique inherits 3-SAT's hardness.