Conjecture 189 of Written on the Wall II
For every connected graph , let denote the second-smallest vertex degree of , and let denote the number of vertices at even distance from . If , then is traceable; that is, contains a spanning path.
References
- Conditions for traceability under a bound on the size of even-distance sets — arXiv — Rohun Easwar, Shaurya Johari
Source: arXiv
Progress summary
A September 2026 paper proves the desired spanning path only under extra restrictions, so the general conjecture remains open.
The conjecture predicts a spanning path under its stated graph-theoretic hypotheses; no proposer or date is identified in the retrieved material.
September 10, 2026 partial progress
Rohun Easwar and Shaurya Johari submitted Conditions for traceability under a bound on the size of even-distance sets. For connected graphs satisfying
the paper proves traceability under one of four additional conditions involving connectivity, order, or diameter. It explicitly presents this as partial progress toward Conjecture 189, not a proof of the general statement.
Current status (as of September 2026): A traceability result is claimed under the stated even-distance bound and additional connectivity, order, or diameter conditions; the general spanning-path conjecture remains open.
Sources
Solutions 0
No solutions have been posted yet.