← All problems

Conjecture 189 of Written on the Wall II

For every connected graph GG, let d2d_2 denote the second-smallest vertex degree of GG, and let dist⁡even(v)\operatorname{dist}_{\mathrm{even}}(v) denote the number of vertices at even distance from vv. If max⁡{dist⁡even(v):v∈V(G)}≤d22+1\max\{\operatorname{dist}_{\mathrm{even}}(v):v\in V(G)\}\le \frac{d_2}{2}+1, then GG is traceable; that is, GG contains a spanning path.

References

Progress summary

Refreshed
Open · progress reported

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 GG satisfying

max⁡{dist⁡even(v):v∈V(G)}≤d22+1,\max\{\operatorname{dist}_{\mathrm{even}}(v):v\in V(G)\}\le \frac{d_2}{2}+1,

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.