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
Conjecture   Do any three longest paths in a connected graph have a vertex in common?

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.

Bibliography

*[G] T. Gallai, Problem 6. In 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.


* indicates original appearance(s) of problem.