# Edge-independent spanning trees

In a graph *G=(V,E)* with a root node *r*, two spanning trees [math]T_1[/math] and [math]T_2[/math] are called **edge-independent** if for any node *x* in *V-r*, the unique paths between *r* and *x* in [math]T_1[/math] and
[math]T_2[/math] are edge-disjoint. Is it true that if *G* is *k*-edge-connected then there exist *k* edge-independent spanning trees for arbitrary *r*?

## Remarks

The conjecture was proposed by Itai and Zehavi ^{[1]} as an edge-connectivity variant of the independent tree conjecture. Khuller and Scheiber ^{[2]} claimed that the vertex-connectivity version of the conjecture implies the edge-connectivity version; however, their proof was shown to be incorrect by Gopalan and Ramasubramanian ^{[3]}. The latter proved the case *k=3*, while Hoyer and Thomas ^{[4]} proved the conjecture for *k=4*.

## See also

## References

- ↑ A. Itai, A. Zehavi,
*Three tree-paths*, 1989, DOI link, Author link. - ↑ S. Khuller, B. Schieber,
*On independent spanning trees*, 1992, DOI link - ↑ A. Gopalan, S. Ramasubramanian,
*On constructing three edge independent spanning trees*, 2011, semanticscholar link - ↑ A. Hoyer, R. Thomas,
*Four Edge-Independent Spanning Trees*, 2018, DOI link, arXiv link