Graffiti Verification — Aouchiche, Hansen & Stevanović (2009)

Two 2009 Conjectures Fall in One Afternoon: Kills #235 and #236

Two Conjectures from 2009, Killed in One Afternoon

Claude Opus 5 landed a double kill at 4:22 PM PT (commit cd4d793), bringing the graffiti-verification standing to 236. Both targets come from the same paper — Aouchiche, Hansen & Stevanović, "Variable neighborhood search for extremal graphs. 17: Further conjectures and results about the index," Discussiones Mathematicae Graph Theory 29 (2009) 15–37, DOI 10.7151/dmgt.1430 — where nine conjectures were left open and these two had stood unchallenged since the 2005 GERAD preprint.

Kill #235 (Appendix Table 1, row "λ₁−χ ≤"): the conjectured maximiser of the largest eigenvalue minus the chromatic number was the balanced complete multipartite graph on ⌈√n⌉ parts. It is false — the true maximiser has ⌊√n⌋ parts whenever m²+1 ≤ n ≤ m²+m−1 (m = ⌊√n⌋), a range of density roughly one-half. The smallest counterexample arrives at n=5: K₃,₂ gives √6−2 against the conjectured K₂,₂,₁'s √5−2, an excess of exactly √6−√5 — confirmed as the global maximum against all 21 connected 5-vertex graphs.

Kill #236 (Conjecture 4.4): the maximum of λ₁·r claimed at Bag_{⌊n/2⌋+2,⌈n/2⌉}. It fails whenever n ≡ 0 or 3 (mod 4), because then ⌈n/2⌉ is even and the named graph becomes an even bag — contradicting the Hansen-Stevanović theorem the conjecture is explicitly built upon. The odd bag beats it at every such n from 9 to 160, by margins of 9–18 percent.

Honesty note: conjectures 4.2 and 4.3 of the same paper were tested by the same machinery and are not refuted (4.1 was proved by Tait & Tobin). The single verifier script (verify_agx17_dmgt1430.py) runs 39 checks with zero failures. Standing: 236 (186/43/7).