Smith's conjecture on longest cycles

Status partial medium confidence

Smith's conjecture that any two longest cycles in a k-connected graph (k ≥ 2) share at least k vertices remains open. Gutiérrez and Valqui (2023) proved that any two longest cycles in a k-connected graph on n vertices intersect in at least min{n, 8k−n−16} vertices, confirming the conjecture when k ≥ (n+16)/7. Ma and Zhao (2025) established an Ω(k^{2/3}) lower bound on the intersection size for general k-connected graphs, and Chen (2026) further improved this to Ω(k^{8/11}) via a forbidden-subdivision approach.

Cited literature (3)

• partial On two conjectures about the intersection of longest paths and cycles (2023)
  Juan Gutiérrez, Christian Valqui · arXiv preprint · arXiv:2310.03849

  Proves that any two longest cycles in a k-connected graph on n vertices intersect in at least min{n, 8k−n−16} vertices, confirming Smith's conjecture for the regime k ≥ (n+16)/7; also addresses the analogous Hippchen conjecture for longest paths.

• partial Intersections of longest cycles in vertex-transitive and highly connected graphs (2025)
  Jie Ma, Ziyuan Zhao · arXiv preprint · arXiv:2508.17438

  Proves that any two longest cycles in a k-connected graph intersect in at least Ω(k^{2/3}) vertices, improving all prior lower bounds; also resolves a 1979 problem of Babai for vertex-transitive graphs.

• partial An Improved Bound for Smith's Longest Cycles Conjecture via a Forbidden Subdivision (2026)
  Douglas M. Chen · arXiv preprint · arXiv:2608.30353

  Improves the best known lower bound on the intersection size of any two longest cycles in a k-connected graph to Ω(k^{8/11}), surpassing the Ω(k^{2/3}) bound of Ma–Zhao, using a Ramsey-theoretic refinement of Turán-type methods.

Reviewer notes. WebSearch was unavailable; all results obtained via WebFetch on arXiv. The three cited papers were found via an arXiv keyword search and each abstract was verified by direct WebFetch. Confidence is medium because the fetched abstracts were summarised by a small model and could not be cross-checked by independent keyword search. The conjecture is related to OPG record chords_of_longest_cycles (Thomassen's chord conjecture for 3-connected graphs, a structurally different statement) and OPG do_any_three_longest_paths_in_a_connected_graph_have_a_vertex_in_common (analogous question for paths). The Gutiérrez–Valqui paper (arXiv:2310.03849) also addresses the Hippchen longest-path conjecture, linking the two problems.

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