K-CONNECTIVITY AND DECOMPOSITION OF GRAPHS INTO FORESTS

We show that, for every k-(edge) connected graph G, there exists a seq uence T1, T2,..., T(k) of spanning trees with the property that T1 or T2 or ... or T(j) is j-(edge) connected for every j = 1,...,k. Nagamoc hi and Ibaraki have recently presented a linear time decomposition pro cedure by which such a sequence of trees can be constructed. We discus s some properties of this procedure and its relation to the arboricity of a graph.