For a finite simple graph G, let alpha(G) denote its independence number and let l_avg(G) = (1 / |V(G)|) sumv in V(G) alpha(G[N_G(v)]) be the average independence number of its open neighbourhoods. Written on the Wall II Conjecture 194 asserts that every simple connected graph on n > 1 vertices satisfying alpha(G) <= 1 + l_avg(G) has a Hamiltonian path. We give a four-parameter family of counterexamples. Its principal two-parameter subfamily satisfies the proposed inequality with equality: for every pair of integers s >= 1 and t >= 3 it has (s + 1)t^2 vertices, independence number t + 1, l_avg(G) = t, and minimum degree s, but has no Hamiltonian path. This entire infinite subfamily is machine-checked in Lean 4: one universally quantified theorem certifies its order, connectivity, independence number, average neighbourhood independence, minimum degree, conjecture hypothesis, and failure of traceability. Thus no fixed lower bound on the minimum degree repairs the conjecture. The case (s,t) = (1,3) has 18 vertices, but the formal certificate is parametric rather than a verification of that one graph alone. Version 1.2 changes, mathematics unchanged from version 1.1. The upstream correction was merged into the Google DeepMind Formal Conjectures repository on 7 August 2026 as pull request 4542, commit 5bc5de9901e7c6b1cb3529fecd88d43a6a66a37a; that repository now records Conjecture 194 as solved with answer(False). Conjecture 194 is now quoted faithfully from the source collection, including its "simple" and "n > 1" hypotheses. The introduction states the exact relationship to Written on the Wall II Conjecture 195, which is the Chvatal-Erdos traceability corollary: Conjecture 194 is the same inequality with l_avg substituted for the connectivity. Six references were added, taking the bibliography from 5 entries to 11. The Lean development is now archived at doi:10.5281/zenodo.22779981.
No takes yet. Share an insight, caveat, or question.
Cameron Beeley (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: