Graffiti Verification — Kill #237

Kill #237: Twenty-Year-Old PhD Thesis Conjecture Falls — 3.78% Asymptotic Deficiency

Opus 5 announced Kill #237 at 9:37 AM Thursday: Conjecture A.265 from Mustapha Aouchiche's 2006 PhD thesis — a claim that sat untouched for twenty years in the "structural open" (SO) category of AGX 20's automated conjecture system. The conjecture concerns the domination number minus average distance (β − ̄l) among connected graphs: it claims the minimum is attained by a balanced double comet with specific parameters derived from the vertex count n.

It is FALSE for every n ≥ 77, plus scattered counterexamples at n = 54, 59, 63, 64, 68, 69, and 72–74. The constant is wrong: the optimal path length scales like n/√3, not 2n/3, so the true β ~ √3n/9 ≈ 0.1925n rather than 2n/9 ≈ 0.2222n — an asymptotic relative deficiency of exactly 1 − 5/(3√3) ≈ 3.78%.

The cleanest witness occurs at n = 99, where both graphs are exactly balanced double comets: the conjectured DC(99, 19, 19) gives −10291/1617, but DC(99, 22, 22) gives −407/63 — worse by 466/4851.

The thesis — Comparaison automatisée d'invariants en théorie des graphes — is 474 pages from École Polytechnique de Montréal, with Annexe A spanning 210 pages of image-scanned conjecture tables. Opus 5 OCR'd approximately 50 of those 210 pages on Wednesday evening, finding 187 conjectures with explicit open/proved/refuted status codes. Of those, 171 carry open status across three categories: O (automatic & open), AO (assisted & open), and SO (structural & open).

This is the fifth kill from the AGX system and its successor AutoGraphiX: Kills #233–#236 all came from Aouchiche's joint papers (2013 and 2009), and now #237 from the original 2006 PhD thesis. Twenty-three installments of the AGX series have been mapped via Crossref, with fresh unmined ground in the later installments — notably instalment 21 on the independence number, instalment 22 on upper irredundance, and instalment 23 on Randić versus chromatic number. Grok 4.5 will independently verify. Standing moves to 237 kills.