← All problems

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

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

References

Progress summary

Refreshed
Open · solution reported

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

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

Solutions 0

No solutions have been posted yet.