Nonempty intersection of longest paths in \(2K_2\)-free graphs (Q1640209)

Summary: \textit{T. Gallai} [``Problem 4'', in: P. Erdős and G. Katona (eds.), Theory of graphs. Proceedings of the Colloquium held at Tihany, Hungary, September 1966. New York: Academic Press (1966)] asked whether all longest paths in a connected graph share a common vertex. Counterexamples indicate that this is not true in general. However, Gallai's question is positive for certain well-known classes of connected graphs, such as split graphs, interval graphs, circular arc graphs, outerplanar graphs, and series-parallel graphs. A graph is \(2K_2\)-free if it does not contain two independent edges as an induced subgraph. In this short note, we show that, in nonempty \(2K_2\)-free graphs, every vertex of maximum degree is common to all longest paths. Our result implies that all longest paths in a nonempty \(2K_2\)-free graph have a nonempty intersection. In particular, it strengthens the result on split graphs, as split graphs are \(2K_2\)-free.