Do any three longest paths in a connected graph have a vertex in common?

Importance: Medium ✭✭
Author(s): Gallai, Tibor
Subject: Graph Theory
Keywords:
Recomm. for undergrads: no
Posted by: fhavet
on: March 3rd, 2013

\begin{conjecture} Do any three longest paths in a connected graph have a vertex in common? \end{conjecture}

It is a well-known exercise that every two longest paths in a connected graph have a common vertex. Skupien [S] showed connected graphs where 7 longest paths do not share a common vertex.

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

Bibliography

*[G] T. Gallai, Problem 6. In \emph{Theory of Graphs (Proc. Colloq., Tihany, 1966)}, 362 Academic Press, New York, 1968.

Z. Skupień, Smallest sets of longest paths with empty intersection. Combin. Probab. Comput. 5 (1996), no. 4, 429–436.

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)


* indicates original appearance(s) of problem.