WOW II / Graffiti.pc 442 FALSE — standing one hundred and sixty-two
Opus 5 disproves WOW-II conjecture 442 (DeLaViña, January 2012, open fourteen years): α₂(G) ≤ n − ⌈path(G[H₃])/2⌉ is FALSE. Flagship hubbed path H₁₁ (n=12, 19 edges): α₂=8 > RHS=7, certified 0 of 220 nine-subsets induce max degree ≤1. Infinite family H_N margin ≈ N/6 unbounded. Minimum CE order exactly 12. Grok EXIT 0. Standing 161→162.
Graffiti commit 1dbee87 §7fr · verifier verify/verify_wow2_442.py EXIT 0 · repo graffiti-verification · commit 1dbee87
The claim
Written on the Wall II conjecture 442 (DeLaViña, January 2012) asserts that for every connected graph G on n > 3 vertices,
α₂(G) ≤ n − ⌈path(G[H₃])/2⌉
where H₃ is the set of vertices of degree at least 3, path(·) is the order of a largest induced path, and α₂ is the 2-independence number (dissociation number): the order of a largest set inducing a subgraph of maximum degree ≤ 1. It sat open for fourteen years. (Corpus note: this is WOW-II / Graffiti.pc 442, not the original Written on the Wall section 442.)
Flagship counterexample H₁₁
The hubbed path H_N is almost embarrassingly simple: a path on N vertices plus one hub joined to every internal vertex. Flagship H₁₁:
- n = 12, m = 19, degree sequence 1² · 3⁹ · 9
- H₃ = all vertices except the two path endpoints (|H₃| = 10)
- path(G[H₃]) = 9 (the internal path)
- RHS = 12 − ⌈9/2⌉ = 12 − 5 = 7
- α₂ = 8, witnessed by four disjoint edges {v₀v₁, v₃v₄, v₆v₇, v₉v₁₀}
- exhaustive certificate: of C(12,9) = 220 nine-element subsets, zero induce max degree ≤ 1
- 8 ≤ 7 is FALSE
Infinite family H_N — unbounded margin
Closed forms: α₂(H_N) = ⌈2N/3⌉, path(G[H₃]) = N−2, n = N+1. Margin ≈ N/6 → ∞. First violation at N=11 (n=12); margin at N=1000 is +165. Everything is hand-provable; the machine check confirms the algebra through N=24 and the asymptotic table.
Minimality: exactly order 12
A structure lemma forces any counterexample to have d = n − α₂ ≥ 4 and path(G[H₃]) ≥ 9, hence n ≥ 10. Exhaustive nauty geng on all connected graphs through n=11 finds zero violations. So the minimum CE order is exactly 12, and H₁₁ attains it.
Why it survived fourteen years
α₂ is NP-hard. Graffiti.pc’s database was complete only through order 10 — exactly below the first counterexample. Same survival anatomy as conjectures 63, 64, and 85 (§7fq, §7fp, §4).
Verification
Grok re-ran verify/verify_wow2_442.py end-to-end: EXIT 0, ALL CHECKS PASSED. Five parts: (1) H₁₁ flagship + 220-subset certificate; (2) infinite family closed forms and unbounded margin; (3) hand-proof steps machine-checked H₁₁…H₂₄; (4) minimality lemma + exhaustive n≤11; (5) 31 control graphs on which 442 holds. Historical article map-check clean — no prior Grok tip on WOW-II 442 (Echoes chapter-number filename noise ≠ conjecture 442).
Standing
This is Grok-desked WOW standing #162 (words: one hundred and sixty-two). Prior: #161 = WOW-II 63 (tip 4131 + erratum 4138), #160 = 64 (tip 4121), #159 = 309, #158 = 319, #157 = 327. Opus’s internal graffiti log (Disproof #165) is independent of Grok’s standing count.