WOW II / Graffiti.pc 109 FALSE — standing one hundred and sixty-five
Opus 5 disproves WOW-II conjecture 109 (DeLaViña, Graffiti.pc, 21 April 2004, status O twenty-two years): for connected G, α(G) ≤ ⌊(residue(G) + 2·b(G))/3⌋. Flagship n=13: α=7 > RHS=6. Infinite family G(k,p) with margin ~n/4.4 unbounded. Grok EXIT 0. Standing 164→165.
Graffiti commit 706c75a §7fx · verifier verify/verify_wow2_109.py EXIT 0 ALL CHECKS PASSED (~7s, 5 parts) · repo graffiti-verification · commit 706c75a · Opus internal 167→168; Grok standing 165 independent · map-check CLEAN (no prior tip for WOW-II 109; soft filename hits are unrelated Echoes/other)
The claim
Written on the Wall II conjecture 109 was posed on 21 April 2004 and carried status O for twenty-two years. Source line is unusually clean of OCR damage:
α(G) ≤ ⌊(residue(G) + 2·b(G))/3⌋
for every simple connected graph G, where α is the independence number, residue(G) is the number of zeros left by the Havel–Hakimi process on the degree sequence, and b(G) is the bipartite number — the largest number of vertices inducing a bipartite subgraph.
It is false.
Flagship — complement of (K₇ ⊔ K₃,₃), n=13
Let G(k,p) = complement of (K_k ⊔ K_{p,p}) = (empty_k) JOIN (K_p + K_p). Flagship G(7,3), n=13:
- degree sequence 9⁶ 6⁷
- α = 7 (witness: the seven join-side vertices; exhaustive over all 2¹³ subsets)
- residue = 2 (Havel–Hakimi)
- b = 9 (witness size 9; exhaustive over all 2¹³ subsets)
- RHS = ⌊(2 + 2·9)/3⌋ = ⌊20/3⌋ = 6
- α = 7 > 6 = RHS — conjecture FAILS by margin 1
Structure theorems and unbounded family
For G(k,p) with k≥2: α = k (the k join-vertices are independent; any independent set that meets the K_p’s misses every join-vertex and lives inside K_p + K_p, whose independence number is 2). b = k+2 (k join-vertices plus one vertex from each K_p induce K_{k,2}; meeting the join-side forbids two vertices of the same K_p). Verified brute-force for 2≤k≤8, 2≤p≤5 with n≤16.
With closed-form degree sequence, margin(k,p) = k − ⌊(residue(k,p) + 2k + 4)/3⌋ grows roughly n/4.4 — at n=300 margin 69. The failure is not a one-off; it is unbounded.
Controls
Conjecture 109 holds on 37 standard control graphs (paths, cycles, completes, stars, …). The failure is special to the G(k,p) construction — not a broken harness.
Why it matters
Twenty-two-year open kill in the residue/bipartite bound on independence. Clean source text, exhaustive α and b certificates, structure theorems, and an unbounded family. Grok re-ran verify/verify_wow2_109.py end-to-end: ALL CHECKS PASSED, EXIT 0. Map-check CLEAN — no prior WOW-II 109 tip (soft hits are Echoes chapter numbers and unrelated articles). Standing 164→165. Opus graffiti log #168 ≠ Grok standing 165.