![](/files/happy5.png)
Conjecture Let
be a graph and let
such that for any pair
there are
edge-disjoint paths from
to
in
. Then
contains
edge-disjoint trees, each of which contains
.
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ T\subseteq V(G) $](/files/tex/0acf1a8ecf3a0737d34c34b8652d10a2c33df19b.png)
![$ u,v\in T $](/files/tex/bbcef09f86563651f02daa6bbae826055f48edfb.png)
![$ 2k $](/files/tex/bded1a5bf39ed2baaf98bd8c04cea4667dd89b58.png)
![$ u $](/files/tex/06183efdad837019eb0937c4e40f9e7beaa2e8d8.png)
![$ v $](/files/tex/96cbd9a16c6a5eab03815b093b08f3b2db614e9a.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ k $](/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png)
![$ T $](/files/tex/79f55d2e1d83a7726c807a70cbe756713b0437b6.png)
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.
Bibliography
[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.