Importance: Medium ✭✭
Author(s): Gallai, Tibor
Subject: Graph Theory
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.


*[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.


Comments are limited to a maximum of 1000 characters.
More information about formatting options