Today’s short post is about Kriesell’s conjecture. In my first year of PhD I enjoyed reading several papers related to this cute conjecture.

Nash-Williams [N’61] and Tutte [Tutte’61] independently proved that a graph has edge-disjoint spanning trees if and only if for every partition of into non-empty classes, where denotes the number of edges connecting distinct classes of . One interesting corollary of this result is the following :

Theorem: Every -edge-connected graph has edge-disjoint spanning trees.

Let be an undirected multigraph and . An is a tree of that contains every vertex in . An is a subset of edges whose removal disconnects some vertices in . A graph is if every has at least edges. Kriesell conjectured the following generalization of the above theorem.

Kriesell’s conjecture: If is , then has edge-disjoint .

The first breakthrough towards proving Kriesell’s conjecture was by Lau. He proved that if *G* is -edge-connected in then it has edge-disjoint Steiner trees. Recently, West and Wu [pdf] proved that it suﬃces for to be -edge-connected in .

Open Problems

- Obvious open problem is to prove or disprove Kriesell’s conjecture.
- There a several related open problems about S-connectors in West-Wu’s paper.

**References :**

**[Tutte’61]**W.T.Tutte :**On the problem of decomposing a graph into n connected factors**,*J. London Math. Soc. 36 (1961), 221–230.***[N’61]**C.St.J.A.Nash-Williams :**Edge disjoint spanning trees of ﬁnite graphs**,*J. London**Math. Soc. 36 (1961), 445–450.***[Lau’07]**L. C. Lau :**An approximate max-Steiner-tree-packing min-Steiner-cut theorem**. Combinatorica 27 (2007), 71–90