FOUR EDGE-INDEPENDENT SPANNING TREES

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 is an element of 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.