{"id":"arxiv/2609.20724","url":"https://arxiv.org/abs/2609.20724","tags":["math.CO"],"score":0,"title":"Longest cycles intersect linearly in highly connected graphs","domain":"math.CO","source":"arxiv","authors":["Jie Ma","Bo Ning","Ziyuan Zhao"],"reviews":0,"subject":"math.CO","summary":"A longstanding conjecture attributed to Smith (1984) asserts that for every $k\\ge2$, any two longest cycles in a $k$-connected graph share at least $k$ vertices. In this paper, we prove the first linear lower bound, showing that any two longest cycles in a $k$-connected graph share at least $k/600$ vertices. Departing from previous Turán-type extremal arguments, we develop a novel structural approach that also yields applications to related problems on longest cycles and paths.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-17","reactions":{}}