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

Every symbol above is now defined; nothing below uses one before this box.

---

The scenario matrix

Every worked example below is tagged with the cell it fills. Read this table first so you can see the whole map before we zoom into any one square. The A-cells run degenerate → yes → no → clique-side, i.e. simplest first.

Cell	Reduction / Object	Kind of input	What it stress-tests
A0	VC ↔ IS duality on the empty graph	degenerate / trivial	$C=\varnothing$, $I=V$ boundary case
A1	VC ↔ IS duality	a "YES" graph	complement identity $C=V\setminus I$
A2	VC ↔ IS duality	a "NO" instance (no small cover)	when the size bound is impossible
A3	Clique ↔ IS ↔ VC full trio via $\bar{G}$	edge-flip	clique-in-$G$ = IS-in-$\bar{G}$ = VC-in-$\bar{G}$
B1	3-SAT ${\le }_p$ Clique	satisfiable formula	one-true-literal-per-clause = clique
B2	3-SAT ${\le }_p$ Clique	unsatisfiable formula ($x\wedge \neg x$ forced)	why no $m$-clique appears
C1	3-SAT ${\le }_p$ Subset Sum	build the number table	digit-column encoding, no carries
D1	Ham-Cycle ${\le }_p$ TSP	graph has a cycle	cheap tour = real cycle, budget $=n$
D2	Ham-Cycle ${\le }_p$ TSP	graph lacks a cycle	why the cheapest tour exceeds $n$
E1	Subset Sum pseudo-polynomial trap	large-number instance	value vs bit-length
F1	Word problem (real world)	scheduling / covering	reading a story into VC

Eleven cells, eleven examples (A0 is the degenerate warm-up, placed first). Every "Forecast:" is revisited in that example's Verify block so you can score your guess.

---

Example 0 — Cell A0 · the degenerate empty graph

Forecast: guess $|C|$ and $|I|$ for a graph with zero edges before reading on.

1. Smallest cover of no edges. A vertex cover must touch every edge; there are none, so the empty set $C=\varnothing$ already covers "all" (zero) edges. $|C|=0$. Why this step? Covering is a "for every edge…" condition — vacuously true when there are no edges.
2. Largest independent set. $I$ needs no edge inside it; with $E=\varnothing$, every vertex can join. $I=\{a,b,c\}=V$, so $|I|=3$. Why this step? Independence forbids internal edges, but there are none to forbid, so all vertices coexist.
3. Test the duality at the boundary. $|C|=n-|I|=3-3=0$. Why this step? We check the identity $C=V\setminus I$ survives the degenerate extreme — cover empty, independent set full.

Verify: $|C|=0$, $|I|=3$, and $0=3-3$ ✔ (numeric, checked in code). Forecast check: if you guessed $|C|=0,|I|=3$, correct — the empty graph is the extreme where the cover vanishes and the independent set swallows everything. ✔

---

Example 1 — Cell A1 · the duality on a "YES" graph

Forecast: before reading on — guess the size of the independent set you'll get, and the size of the largest clique. (Hint: $n=5$.)

Figure 1 (below) shows this graph: amber dots are the cover $C=\{a,c,d\}$, cyan dots are the leftover independent set $I=\{b,e\}$.

1. List what must be touched. Edges are $ab,bc,ca,cd,de$. Why this step? A vertex cover is defined as "a set touching every edge", so we must first know the edge list precisely.
2. Pick the busy vertex $c$. $c$ sits on $bc,ca,cd$ — three of the five edges (the amber hub in Figure 1). Why this step? High-degree vertices cover the most edges per pick; greedy start.
3. What is left uncovered? After $c$: edges $ab$ and $de$ remain. Why this step? You cannot stop until every edge is touched, so we track the remainder.
4. Cover $ab$ and $de$ with two more vertices. Add $a$ (kills $ab$) and $d$ (kills $de$). Cover $C=\{a,c,d\}$, size 3. Why this step? $ab$ and $de$ share no vertex, so they genuinely need two separate picks.
5. Read the complement independent set. $I=V\setminus C=\{b,e\}$ (the cyan dots in Figure 1). Why this step? The duality identity $I=V\setminus C$ says the leftovers of a cover form an independent set.
6. Read the clique side of the trio. The vertices $\{a,b,c\}$ have all three edges $ab,bc,ca$ present — a clique of size 3. Why this step? This is the clique member of "Clique ↔ VC ↔ IS": a set that is pairwise adjacent in $G$, completing the trio the matrix promised.

Verify:

• Cover check: $ab$ (has $a$) ✔, $bc$ (has $c$) ✔, $ca$ (has $c,a$) ✔, $cd$ (has $c,d$) ✔, $de$ (has $d$) ✔. All five covered.
• Independence check: is there an edge between $b$ and $e$? Scan the list — no $be$. So $\{b,e\}$ is independent. ✔
• Clique check: $ab,bc,ca$ all present, so $\{a,b,c\}$ is a $3$-clique. ✔
• Arithmetic (numeric, code-checked): $|C|=n-|I|=5-2=3$. ✔
• Forecast check: independent set size $2$, largest clique size $3$. If you guessed those, well done. ✔

---

Example 2 — Cell A2 · a "NO" instance (the bound is impossible)

Forecast: guess yes or no first.

1. A size-1 cover means one vertex touches every edge. Why this step? That's the literal definition with $k=1$ — one chosen vertex must sit on all five edges.
2. Find the max degree. Degrees: $a$ has $\{ab,ca\}=2$; $b$ has $\{ab,bc\}=2$; $c$ has $\{bc,ca,cd\}=3$; $d$ has $\{cd,de\}=2$; $e$ has $\{de\}=1$. Why this step? The best single vertex covers exactly its degree-many edges; nothing can cover more.
3. Compare to edge count. Highest degree is $3$ (vertex $c$), but there are $5$ edges. One vertex covers at most $3<5$. Why this step? If the best possible single pick still misses edges, no size-1 cover exists.

Verify: even the best vertex $c$ leaves $ab$ and $de$ uncovered — $2$ edges orphaned; $\max \text{degree}=3<5$ edges (numeric, code-checked). So NO, minimum vertex cover $\ge 2$ here (in fact the true minimum is $3$, found in Ex. 1). ✔ Forecast check: the answer is NO; the degree bound rules out $k=1$ cleanly.

---

Example 3 — Cell A3 · the full Clique ↔ IS ↔ VC trio via the complement graph

Forecast: guess — clique of size 3 in a graph with only 2 edges: possible or not?

Figure 2 (below): left = $G$ (cyan edges $pq,rs$); right = $\bar{G}$ (amber dashed edges $pr,ps,qr,qs$).

1. Recall the identity. $G$ has a clique of size $k⟺\bar{G}$ has an independent set of size $k$. Why this step? A clique in $G$ is a set all-connected in $G$, i.e. all-disconnected in $\bar{G}$ — that is precisely an independent set of $\bar{G}$. We will now hunt in $\bar{G}$.
2. Build $\bar{G}$. On $4$ vertices there are $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ possible edges. $G$ uses $pq,rs$, so $\bar{G}$ has the other four: $pr,ps,qr,qs$. Why this step? The complement contains exactly the non-edges of $G$ (the amber dashed lines in Figure 2).
3. Search $\bar{G}$ for an independent set of size 3 — ALL four subsets. There are exactly $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ three-element subsets; we test each:
   • $\{p,q,r\}$: contains $pr\in \bar{G}$ → has an edge → not independent.
   • $\{p,q,s\}$: contains $qs\in \bar{G}$ → has an edge → not independent.
   • $\{p,r,s\}$: contains $pr\in \bar{G}$ → has an edge → not independent.
   • $\{q,r,s\}$: contains $qr\in \bar{G}$ → has an edge → not independent. Every one of the four fails, so no independent 3-set exists in $\bar{G}$. Why this step? Enumerating all $4$ subsets makes the "no" watertight — no case is skipped.
4. Cross-check via the vertex cover of $\bar{G}$. By duality, an IS of size $3$ in $\bar{G}$ would mean a VC of size $n-3=1$ in $\bar{G}$. But $\bar{G}$'s edges $pr,ps,qr,qs$ have max degree $2$ (each of $p,q,r,s$), and $2<4$ edges, so no single vertex covers all four — no size-1 cover, confirming no size-3 IS. Why this step? This is the VC member of the trio, giving an independent second route to the same verdict.
5. Translate back. No independent set of size 3 in $\bar{G}$ ⇒ no clique of size 3 in $G$. Why this step? The identity from step 1 turns the $\bar{G}$ result into the $G$ answer.

Verify: the largest independent set in $\bar{G}$ is size $2$ (e.g. $\{p,q\}$: is $pq\in \bar{G}$? no — so $\{p,q\}$ is independent in $\bar{G}$, matching the clique $pq$ in $G$). Hence max clique in $G$ $=2<3$: NO. All four 3-subsets contained a $\bar{G}$-edge (numeric enumeration, code-checked). ✔ Forecast check: impossible — a 3-clique needs each member joined to the other two, but $G$'s densest structure is a single edge. ✔

---

Example 4 — Cell B1 · 3-SAT ${\le }_p$ Clique on a satisfiable formula

Forecast: guess how many vertices the gadget has, and whether a size-3 clique exists.

Figure 3 (below): three rows = three clauses; the amber triangle is the chosen size-3 clique that gives $x=T,z=T$.

1. Make $3m$ vertices. $m=3$ clauses × $3$ literals $=9$ vertices, grouped in triples $C_1=\{x,y,\neg z\}$, $C_2=\{\neg x,\neg y,z\}$, $C_3=\{x,\neg y,z\}$. Why this step? One vertex per literal-occurrence is the fixed recipe.
2. Add edges = "compatible + different clause". Connect $u,v$ iff they are in different clauses AND are not a $x/\neg x$ pair. Why this step? An edge means "these two literals can be true at the same time and belong to distinct clauses" — exactly what a clause-by-clause selection needs.
3. Look for a 3-clique = one vertex per clause, all compatible. Try $x$ from $C_1$, $z$ from $C_2$, $z$ from $C_3$ (the amber triangle in Figure 3). Check pairs: $x$(C1)–$z$(C2) different clause, not negations ✔; $x$(C1)–$z$(C3) ✔; $z$(C2)–$z$(C3) ✔. Triangle found. Why this step? A size-$m$ clique must pick one per clause (no intra-clause edges), and mutual edges guarantee no contradiction.
4. Read the assignment. Chosen literals $x,z,z$ ⇒ set $x=\text{true},z=\text{true}$; $y$ is free (say $\text{true}$). Why this step? The clique tells us which literal makes each clause true.

Verify: with $x=T,y=T,z=T$:

• $C_1=(x\vee y\vee \neg z)=(T\vee T\vee F)=T$ ✔
• $C_2=(\neg x\vee \neg y\vee z)=(F\vee F\vee T)=T$ ✔
• $C_3=(x\vee \neg y\vee z)=(T\vee F\vee T)=T$ ✔

Formula satisfied (code-checked), matching the found 3-clique. ✔ Forecast check: $9$ vertices, and yes, a size-3 clique exists. ✔

---

Example 5 — Cell B2 · 3-SAT ${\le }_p$ Clique on an UNsatisfiable formula

Forecast: guess — can any vertex in clause 1 connect to any vertex in clause 2?

1. Enumerate vertices. $C_1=\{x_a,x_b,x_c\}$ (all the literal $x$), $C_2=\{\neg x_a,\neg x_b,\neg x_c\}$ (all $\neg x$). Why this step? Repeated literals still get their own vertices — the recipe is per occurrence.
2. Try to draw any cross-clause edge. Every $C_1$ vertex is $x$; every $C_2$ vertex is $\neg x$. An edge needs "not a negation pair" — but every cross pair is $x$ vs $\neg x$. So zero cross edges. Why this step? Contradicting literals are exactly what the construction refuses to connect.
3. Count possible cliques. A size-2 clique needs one vertex from each clause (intra-clause edges don't exist either, since same clause). With no cross edges, no 2-clique exists. Why this step? No edge ⇒ no clique of size $\ge 2$.

Verify: logically $\psi$ requires $x=T$ (clause 1) and $x=F$ (clause 2) simultaneously — impossible (a purely logical verdict). Cross edges drawn $=0$ (numeric, code-checked). Both the logic and the empty-edge gadget say UNSAT. ✔ Forecast check: no cross-clause edge can be drawn (every pair is $x$ vs $\neg x$). ✔

---

Example 6 — Cell C1 · 3-SAT ${\le }_p$ Subset Sum number table

Forecast: using the fixed layout [var | clause], guess the target's two digits.

Number	var-$x$	clause-$C_1$	decimal value $=10\cdot \text{var}+\text{clause}$
$T_x$ (means $x=T$, $x$ appears positively)	1	1	11
$F_x$ (means $x=F$)	1	0	10
slack $s$ (top-up $=L-1=2$)	0	2	2
target $t$	1	3	13

1. Variable column must equal 1. Pick exactly one of $T_x,F_x$. Why this step? Target digit $1$ forces "each variable chosen once" — true XOR false, never both, never neither.
2. Clause column must equal 3. $x$ appears positively in $C_1$, so a true $x$ ($T_x$) contributes $1$ to the clause column; the single slack $s$ contributes $2$; total $1+2=3$. Max column sum here is $1+2=3<10$, so no carry corrupts the variable column — the layout stays clean. Why this step? Target digit $3$ = "at least one literal satisfied ($\ge 1$), then slack tops up to $3$."
3. Assemble the subset by the fixed layout. Choose $\{T_x,s\}$: var column $=1$, clause column $=1+2=3$, so the number is $(1)(3)=10\cdot 1+3=13=t$. Why this step? We read the columns in the pre-fixed order [var|clause], so the value is unambiguously $13$, never $31$.
4. Check the FALSE branch is rejected — this is why slacks are capped. Choose $\{F_x,s\}$: var column $=1$ ✔ but clause column $=0+2=2\ne 3$. Value $=10+2=12\ne 13$. Why this step? $F_x$ means $x=$false, so clause $(x)$ is unsatisfied; the slack alone ($2=L-1$) cannot reach $3$, so the target correctly refuses it.

Verify: $T_x+s=11+2=13=t$ ✔ (true assignment accepted); $F_x+s=10+2=12\ne 13$ ✔ (false assignment rejected). Both numeric, code-checked. The accepting subset $\{T_x,s\}$ corresponds to $x=\text{true}$ satisfying $(x)$. ✔ Forecast check: the target's digits are $1$ (var) and $3$ (clause), value $13$. ✔

---

Example 7 — Cell D1 · Ham-Cycle ${\le }_p$ TSP, graph WITH a cycle

Forecast: guess the cheapest tour cost, and whether it is $\le B$.

Figure 4 (below): cyan solid edges cost $1$ (real), amber dashed diagonals cost $2$ (missing).

1. Complete the graph. On $4$ vertices, missing edges are the two diagonals $ac,bd$. Real edges $ab,bc,cd,da$ get weight $1$; diagonals $ac,bd$ get weight $2$. Why this step? TSP runs on a complete weighted graph, so we must price every pair.
2. Set budget $B=n=4$. Why this step? A tour is a cycle over all $n$ vertices returning home, using exactly $n$ edges. If all are real (weight 1) the cost is exactly $n$; that's the cheapest achievable.
3. Trace the tour $a\to b\to c\to d\to a$. Weights $1+1+1+1=4$ (the cyan loop in Figure 4). Why this step? This tour uses only real edges, so its cost equals the budget — the "yes" witness.

Verify: cost $=4=B$ ✔ (numeric, code-checked), and every vertex visited exactly once then return ✔. The tour uses only weight-1 (real) edges, so it is a Hamiltonian cycle of $G$. Any tour touching a diagonal would cost $\ge 3(1)+2=5>4$. ✔ Forecast check: cheapest tour $=4$, exactly at budget. ✔

---

Example 8 — Cell D2 · Ham-Cycle ${\le }_p$ TSP, graph WITHOUT a cycle

Forecast: guess the minimum tour cost.

1. Price the complete graph. Real edges $ab,bc,cd$ (weight 1). Missing: $ac,bd,ad$ (weight 2). Why this step? Same recipe — every non-edge costs $2$.
2. Any tour of 4 vertices uses 4 edges and must return to start. The path has only 3 real edges forming a line, not a loop; endpoint $a$ has only one real edge ($ab$), so its second tour-edge must be a weight-2 one. Why this step? In a cycle every vertex needs two tour-edges; $a$ cannot supply a second real one.
3. Best case cost. Tour $a\to b\to c\to d\to a$: $ab(1)+bc(1)+cd(1)+da(2)=5$; any other ordering forces at least one weight-2 edge too, and checking all orderings confirms $5$ is the minimum. Why this step? We forced $\ge 1$ weight-2 edge; this arrangement uses exactly one, so it is optimal.

Verify: the minimum over all tour orderings is $5$ (numeric, code-checked by brute force). Since $5>4=B$, NO tour fits the budget, hence NO Hamiltonian cycle in $H$. ✔ Consistent: a path graph genuinely has no Hamiltonian cycle. Forecast check: cheapest tour $=5$, one above budget. ✔

---

Example 9 — Cell E1 · the pseudo-polynomial trap

Forecast: guess which subset works (or whether none does).

1. Spot the big number. $t=1000000014$ and $1000000007\in S$. Subtract: $t-1000000007=7$. Why this step? The target is barely above one element; if we include it, the remainder $7$ must come from the small numbers.
2. Try to hit remainder 7 from $\{2,4,8\}$. All of $2,4,8$ are even, so every subset sum of them is even; $7$ is odd, so it is unreachable. Why this step? A parity check instantly rules out the "include the big number" branch.
3. Try excluding the big number. Then we need $t=1000000014$ from $\{2,4,8\}$, whose largest possible sum is $2+4+8=14\ll t$. Impossible. Why this step? We must check both branches (include / exclude the big element) to be sure.

Verify: reachable sums are $\{0,2,4,6,8,10,12,14\}$ (small only) and $\{1000000007+e:e\in \{0,2,4,6,8,10,12,14\}\}$ (with the big number). $1000000014$ is in neither list (numeric, code-checked by full enumeration). NO subset sums to $t$. ✔ Forecast check: no subset works — parity + magnitude both block it. ✔

---

Example 10 — Cell F1 · word problem → Vertex Cover (real-world scheduling)

Forecast: the pentagon has 5 corridors — guess the minimum number of guarded rooms.

Figure 5 (below): the pentagon of rooms; amber dots are the chosen guard posts $\{a,c,d\}$.

1. Translate the story into a graph. Rooms = vertices $V$, corridors = edges $E$, "watch every corridor" = cover every edge ⇒ this is Vertex Cover on a 5-cycle. Why this step? Recognising the abstract problem is the whole point of a reduction — the real-world story is just a costume over the graph problem.
2. Lower bound (how few can possibly work). A 5-cycle has $5$ edges; one guard covers at most $2$ corridors (each room touches 2), so we need $\ge \lceil 5/2\rceil =3$ guards. Why this step? Total edges divided by max-edges-per-vertex gives an unavoidable minimum.
3. Build a size-3 cover. Post guards at $\{a,c,d\}$ (amber in Figure 5): $a$→$ab,ea$; $c$→$bc,cd$; $d$→$cd,de$. Covered corridors: $ab,ea,bc,cd,de$ = all 5. Why this step? We match the lower bound with an explicit set, proving $3$ is optimal.

Verify: guard set $\{a,c,d\}$ touches every corridor ✔; and $3$ meets the $\lceil 5/2\rceil =3$ lower bound, so no smaller set exists (numeric, code-checked). 3 guards. ✔ Its complement $\{b,e\}$ is an independent set of size $2=n-3$, matching $I=V\setminus C$. Forecast check: the answer is $3$, not $2$ (a 5-cycle's minimum cover is $\lceil 5/2\rceil =3$). ✔

---

Recall Self-test (reveal answers)

Empty graph on 3 vertices — sizes of min cover and max independent set? ::: $|C|=0$, $|I|=3$; duality $0=3-3$. Size-1 cover on the 5-edge graph of Ex.1 — possible? ::: No; max degree $3<5$ edges. In the 3-SAT→Clique gadget, why no edge between $x$ and $\neg x$? ::: Choosing both is a contradiction; they can't be true together. How much must a clause's slack numbers sum to, and why? ::: Exactly $L-1$, so slacks alone can never satisfy an unsatisfied clause. TSP budget for Ham-Cycle reduction on $n$ vertices? ::: $B=n$ (a tour is a cycle using exactly $n$ edges). Why is Subset Sum's $O(n\cdot t)$ DP not polynomial? ::: $t$ is exponential in its bit-length $\log t$; it's pseudo-polynomial. Pentagon museum minimum guards? ::: 3.