The paper disproves a conjecture in graph theory called "Written on the Wall II Conjecture 194." The conjecture was about a relationship between a graph's structure and whether it contains a Hamiltonian path, which is a route that visits every vertex in the graph exactly once. Specifically, the conjecture claimed that any connected graph satisfying certain conditions about independence numbers (the size of the largest set of vertices with no edges between them) and average neighborhood independence must always have a Hamiltonian path. The paper shows this is false by constructing an infinite family of graphs that satisfy all the required conditions but nonetheless fail to have a Hamiltonian path.
The counterexample family is parameterized by two numbers, s and t, where t must be at least 3. Each graph in this family has a specific number of vertices, independence number, average neighborhood independence, and minimum degree that together satisfy exactly the conditions the conjecture requires. Because the family is infinite, the failure is not an isolated accident or a quirk of one particular graph. Crucially, the authors also show that no matter how large you require the minimum degree to be, you can still find a counterexample in this family, meaning the conjecture cannot be salvaged simply by adding a stronger degree condition.
What makes the paper especially notable is that the counterexamples are formally verified using Lean 4, a computer proof assistant. Rather than just checking one specific graph, the authors wrote a single general theorem that covers all graphs in the infinite family at once, confirming every relevant property including connectivity, independence numbers, and the absence of a Hamiltonian path. This machine-checked certificate means there is essentially no room for human error in the disproof, and it demonstrates a practical way to use formal verification tools to settle questions in combinatorics involving infinite families of objects.