Four Edge-Independent Spanning Trees
Alexander Hoyer, Robin B. Thomas · SIAM Journal on Discrete Mathematics · 2018
We prove an ear-decomposition theorem for 4-edge-connected graphs and use it to prove that for every 4-edge-connected graph $G$ and every $r\in V(G)$, there is a set of four spanning trees of $G$ with the following property. For every vertex in $G$, the unique paths back to $r$ in each tree are edge-disjoint. Our proof implies a polynomial-time algorithm for constructing the trees.