ABSTRACT
A problem which occurs in varying contexts is to determine whether a given graph can be decomposed into line-disjoint spanning subgraphs possessing a prescribed property. Some observations are presented concerning the decomposition of complete graphs into spanning subgraphs regular of degree 1 and 2. The partitioning of the lines of a given graph into spanning forests is also studied and gives rise to an invariant known as "arboricity." A formula for the arboricity of a graph in terms of its subgraphs was derived by Nash-Williams, and explicit constructions for the minimum number of spanning forests in complete graphs and bigraphs have been devised. Although Nash-Williams' formula gives the minimum number of spanning forests into which an arbitrary graph can be factored, his proof does not display a specific decomposition. The most significant result on factorization is due to W. T. Tutte and characterizes graphs possessing a 1-factor.
