Matthews–Sumner conjecture

Status partial high confidence

The Matthews–Sumner conjecture (every 4-connected claw-free graph is Hamiltonian, 1984) remains open as of September 2026. Via Ryjáček's 1997 closure theorem it is equivalent to Thomassen's conjecture that every 4-connected line graph is Hamiltonian, also open. The strongest known partial result is Kaiser and Vrána (2012), who proved that every 5-connected line graph of minimum degree at least 6 is Hamiltonian, improving the previous threshold from 7-connected. A 2026 paper by Ozeki and Zhang addresses Hamiltonicity in 3-connected claw-free graphs with small domination number, motivated by Thomassen's conjecture, but does not resolve the 4-connected case.

Cited literature (2)

• partial Hamilton cycles in 5-connected line graphs (2012)
  Kaiser, Tomáš; Vrána, Petr · Journal of Combinatorial Theory, Series B · arXiv:1009.3754

  Proves that every 5-connected line graph of minimum degree at least 6 is Hamiltonian (and the result extends to claw-free graphs and Hamilton-connectedness), improving the previously known threshold of 7-connectivity but falling short of the conjectured 4-connectivity.

• partial Hamiltonian Properties of 3-Connected Claw-Free Graphs and Line Graphs of 3-Hypergraphs (2026)
  Ozeki, Kenta; Zhang, Leilei · arXiv preprint · arXiv:2603.03361

  Proves that every 3-connected claw-free graph with domination number at most 5 is Hamiltonian (with limited exceptions), motivated by Thomassen's line graph conjecture; does not address the Matthews–Sumner conjecture for 4-connected graphs.

Reviewer notes. The conjecture is equivalent to Thomassen's conjecture (every 4-connected line graph is Hamiltonian) via Ryjáček's closure (1997), already noted in the book and tracked in OPG record hamiltonian_cycles_in_line_graphs. Searches were hampered by intermittent WebSearch failures; the arXiv and Open Problem Garden were consulted directly. No paper claiming a proof or counterexample of the full conjecture was found. The Kaiser–Vrána result (arXiv 1009.3754) is the key post-2008 partial result; its published form appeared in J. Combin. Theory Ser. B 103 (2013) 461–477 (year cited as 2012 matching arXiv submission year commonly used). The Ozeki–Zhang 2026 preprint is included as the most recent work motivated by the same circle of conjectures.

Auto-reviewed 2026-09-10 with claude-sonnet-4-6 (web search enabled).