We construct decompositions of L(K,,), M(K,,) and T(K,,) into the minimum number of line-disjoint spanning forests by applying the usual criterion for a graph to be eulerian. This gives a realization of the arboricity of each of these three graphs.
1. Preliminaries
In this paper a graph is considered as finite, undirected, with single lines and no loops.
The arboricity of a graph G, denoted by Y(G), is the least number of line-disjoint spanning forests into which G can be partitioned. {x} is the least integer not less than X, and A(G) is the maximum degree among the points of G. V(G), E(G), and ISI denote the point set of G, the line set of G, and the number of elements of a set S!, respectively. L(G), M(G) and T(G) denote the line graph of G, the middle graph of G (see [3]), and the total graph of G respectively. Other definitions no* presented here may be found in [4]. Later on, the following two Theorems will be applied. Theorem A (C.St.J.A. Nash-Williams, [S, 61). Let G be a nonttivial (p, q)-graph and let qk be the maximum number of lines in any subgraph of G having k points, then Y(G) = max {qk/(k -1)).
I<ksp heore (L.W. Beineke, [2]). For the complete graph K,,,