For every finite simple connected graph G with |V(G)|>1, if alpha(G)≤ 1+ell_avg(G), where alpha(G) is the independence number of G and ell_avg(G)=frac1|V(G)|∑_v∈ V(G)alpha bigl(G[N_G(v)]bigr) with N_G(v) the open neighborhood of v, then G has a Hamiltonian path.

Written on the Wall II Conjecture (Erdős problem #194)

For every finite simple connected graph $G$ with $|V(G)|>1$ , if $\alpha(G)\le 1+\ell_{\mathrm{avg}}(G)$ , where $\alpha(G)$ is the independence number of $G$ and $\ell_{\mathrm{avg}}(G)=\frac{1}{|V(G)|}\sum_{v\in V(G)}\alpha\bigl(G[N_G(v)]\bigr)$ with $N_G(v)$ the open neighborhood of $v$ , then $G$ has a Hamiltonian path.

References

Primary source

Zenodo

Additional references

Lean-Certified Infinite Counterexamples to Written on the Wall II Conjecture 194 — Zenodo — Cameron Beeley

Posted 3 weeks ago · edited 3 weeks ago

Progress summary

Refreshed 3 weeks ago

Claimed solved

A deposited report claims to disprove the conjecture with computer-certified counterexamples, but the result has not been independently verified.

The problem concerns the Written on the Wall II Conjecture, catalogued as Erdős problem #194; the retrieved sources do not restate the conjecture or give its proposer or date.

September 2026 claimed disproof

On September 16, 2026, Cameron Beeley’s Zenodo deposit Lean-Certified Infinite Counterexamples to Written on the Wall II Conjecture 194 reported infinite counterexamples with Lean certification. This would disprove the conjecture if the formalized statement matches the original, but the record supplies neither the formal statement nor proof details.

Current status (as of September 2026): A claimed disproof exists, but the conjecture is not verified as false because the formal statement, certification, and correspondence with the original conjecture have not been independently checked.

Sources

No solutions have been posted yet.