On the Intersections of Longest Cycles in a Graph

Abstract

We confirm a conjecture, due to Grötschel, regarding the intersection vertices of two longest cycles in a graph. In particular, we show that if G is a graph of circumference at least k + 1, where k ∊ {6,7}, and G has two longest cycles meeting in a set W of k vertices, then W is an articulation set. Grötschel had previously proved this result for k ∊ {3,4,5} and shown that it fails for k > 7. As corollaries, we obtain results regarding the minimum lengths of longest cycles in certain vertex-transitive graphs. Our proofs are novel in that they make extensive use of a computer, although the programs themselves are straightforward.