# Independent trees

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

## Remarks

It has been showed[1][2][3] that the conjecture holds for k=2,3. The case when k=4 was also verified[4] but for $k\geq 5$ the problem is still open.

Concerning planar graphs, Huck proved[5][6] the statement for each $k\geq1$, i.e. we have

Theorem For a rooted k-connected undirected planar multigraph and $r\in V(G)$ there exist k r-independent spanning trees in G.

Planar multigraphs are handleable even in the directed case. Huck proved[7] a strengthening of these theorems where the connectivity condition is weakened to rooted connectivity. By summarizing the mentioned results we have the following.

Theorem

(i) Let D be a rooted k-connected directed multigraph for some root $r\in V(G)$ and $k\in\{1,2\}\cup\{6,7,8,...\}$ such that D is planar if $k\geq 6$. Then D contains k independent spanning arborescences of root r.

(ii) Let G be a rooted k-connected undirected multigraph for some root $r\in V(G)$ and $k\geq 1$ such that G is planar if $k\geq 5$. Then G contains k r-independent spanning trees.

### Strongly independent spanning trees

A further strengthening of this concept is strongly independent trees: two spanning trees $T_1$ and $T_2$ are called strongly independent if for any two nodes x,y in V, the unique paths between x and y in $T_1$ and $T_2$ are internally node disjoint. Hasunuma[8] posed the following conjecture:

Conjecture. Is it true that any 2k-connected graph contains k strongly independent spanning trees?

This has been disproved by Péterfalvi[9] by showing that for any k there exist a k-connected graph not containing two strongly independent spanning trees.