A finite consistency check of Written-on-the-Wall conjectures 20 and 21 on all connected graphs with 4 <= n <= 11 (the statement is claimed proved)

Since the adjacency matrix has trace 0, S+ = E/2 (E the graph energy), so Written-on-the-Wall (Graffiti) conjectures 20 (n+ ≤ S+) and 21 (n- ≤ S+) are together exactly E(G) ≥ 2 max(n+, n-). This is a finite consistency check of a claimed theorem, not a new result. Kumar and Pragada (arXiv:2607.19817, 22 Jul 2026, unrefereed, AI used for ideation; we did not check the proof) claim E(G) ≥ 2(n − α(G)) (Fajtlowicz's Graffiti #543) and deduce E ≥ 2 max(n+, n-), which they state resolves Aouchiche–Hansen 2010 Conjectures #20 and #21. The smaller-count version has been a theorem since Fajtlowicz 1987 (E ≥ rank). What was run. All 1,018,690,325 connected graphs with 4 ≤ n ≤ 11 (nauty geng) were scanned in double precision (Tier X): 0 violations of 20 or 21. Among connected graphs conjecture 21 is tight only at Kn (n ≤ 10 exhaustively; n = 11 through a flag band); these ties were decided exactly from the integer characteristic polynomial (Tier C). The smallest non-Kn margins for 21 are certified and shrink with n: 0.2143, 0.1463, 0.1249, 0.0941, 0.0806, 0.0645, 0.0561 for n = 5..11. For n ≤ 3, K1 and K2 give equality in both conjectures, so the range starts at 4. A positive control (Graffiti 29, disproved in 1988, first fires at n = 7) and two negative controls (theorems, fire 0 times) were run. Audit. A separate AI agent instance (not a human) recomputed all n ≤ 10 and 12.2% of n = 11 (122,811,341 graphs) with different code and exact inertia: all match, 0 violations (ACCEPT_WITH_CORRECTIONS; eight corrections applied). Every nonzero adjacency eigenvalue for n ≤ 11 satisfies |λ| ≥ 6.2e-6, so the 1e-9 threshold gives exact inertia assuming LAPACK backward stability; the scan is not interval-certified. Limitations. The Kumar–Pragada proof was not checked; 35 of 40 n = 11 parts were not independently recomputed; other WoW conjectures (39, 40, 129, 143, 154, 195, 284, 698) remain blocked because their definitions were not pinned; no Lean; no human audit.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-01
DOI
https://doi.org/10.5281/zenodo.23856041
Primary Topic
Graph theory and applications
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

A finite consistency check of Written-on-the-Wall conjectures 20 and 21 on all connected graphs with 4 <= n <= 11 (the statement is claimed proved)

Xavier Callens
1 links
Zenodo (CERN European Organization for Nuclear Research)
Graph theory and applications
preprint

A finite consistency check of Written-on-the-Wall conjectures 20 and 21 on all connected graphs with 4 <= n <= 11 (the statement is claimed proved)

Xavier Callens
preprint en

Abstract

Since the adjacency matrix has trace 0, S+ = E/2 (E the graph energy), so Written-on-the-Wall (Graffiti) conjectures 20 (n+ ≤ S+) and 21 (n- ≤ S+) are together exactly E(G) ≥ 2 max(n+, n-). This is a finite consistency check of a claimed theorem, not a new result. Kumar and Pragada (arXiv:2607.19817, 22 Jul 2026, unrefereed, AI used for ideation; we did not check the proof) claim E(G) ≥ 2(n − α(G)) (Fajtlowicz's Graffiti #543) and deduce E ≥ 2 max(n+, n-), which they state resolves Aouchiche–Hansen 2010 Conjectures #20 and #21. The smaller-count version has been a theorem since Fajtlowicz 1987 (E ≥ rank). What was run. All 1,018,690,325 connected graphs with 4 ≤ n ≤ 11 (nauty geng) were scanned in double precision (Tier X): 0 violations of 20 or 21. Among connected graphs conjecture 21 is tight only at Kn (n ≤ 10 exhaustively; n = 11 through a flag band); these ties were decided exactly from the integer characteristic polynomial (Tier C). The smallest non-Kn margins for 21 are certified and shrink with n: 0.2143, 0.1463, 0.1249, 0.0941, 0.0806, 0.0645, 0.0561 for n = 5..11. For n ≤ 3, K1 and K2 give equality in both conjectures, so the range starts at 4. A positive control (Graffiti 29, disproved in 1988, first fires at n = 7) and two negative controls (theorems, fire 0 times) were run. Audit. A separate AI agent instance (not a human) recomputed all n ≤ 10 and 12.2% of n = 11 (122,811,341 graphs) with different code and exact inertia: all match, 0 violations (ACCEPT_WITH_CORRECTIONS; eight corrections applied). Every nonzero adjacency eigenvalue for n ≤ 11 satisfies |λ| ≥ 6.2e-6, so the 1e-9 threshold gives exact inertia assuming LAPACK backward stability; the scan is not interval-certified. Limitations. The Kumar–Pragada proof was not checked; 35 of 40 n = 11 parts were not independently recomputed; other WoW conjectures (39, 40, 129, 143, 154, 195, 284, 698) remain blocked because their definitions were not pinned; no Lean; no human audit.

Zenodo (CERN European Organization for Nuclear Research)
Graph theory and applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
A finite consistency check of Written-on-the-Wall conjectures 20 and 21 on all connected graphs with 4 <= n <= 11 (the statement is claimed proved) — Xavier Callens · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS