Paperlane

no. 10 · Friday 6 November 2026

An improved bound for the intersection of two longest cycles in $k$-connected graphs

Juan Gutiérrez

math.CO

Abstract

A conjecture attributed to Smith states that in every $k$-connected graph, every pair of longest cycles intersects in at least $k$ vertices. We prove that every two longest cycles in a $k$-connected graph on $n$ vertices intersect in at least $\min\{k,10k-n-30\}$ vertices. Consequently, Smith's conjecture holds whenever $k\ge \frac{n+30}{9}$. This improves the previous bound of $\frac{n+16}{7}$ for $n>33$ and also implies a bound of $\frac{n+22}{9}$ for paths instead of cycles.

fields
Combinatorics
pdf ↗ page arXiv:2611.07145 ↗