Kriesell's Conjecture

Importance: Medium ✭✭
Author(s): Kriesell, Matthias
Recomm. for undergrads: no
Posted by: Jon Noel
on: August 25th, 2013
Conjecture   Let $ G $ be a graph and let $ T\subseteq V(G) $ such that for any pair $ u,v\in T $ there are $ 2k $ edge-disjoint paths from $ u $ to $ v $ in $ G $. Then $ G $ contains $ k $ edge-disjoint trees, each of which contains $ T $.

This problem was featured as unsolved problem #22 in Bondy and Murty's book "Graph Theory" [BM].

See also a posting on the open problem forum of the Egerváry Research Group on Combinatorial Optimization.


[BM] J. A. Bondy and U. S. R. Murty. Graph theory, volume 244 of Graduate Texts in Mathematics. Springer, New York, 2008.

* indicates original appearance(s) of problem.