login/create account
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.
Drupal
CSI of Charles University