Given a graph $G$, it is possible to construct a sequence $H\_1, H\_2, \dotsc, H\_k$ of graphs each a set of disjoint edges (i.e., every vertex of degree at most $1$) with $G = \bigcup H\_i$.


For example:


For the complete bipartite graph $K\_{n,n}$, only $n$ graphs are needed, which can be seen by taking one perfect matching, and then fixing one set and cyclically rotating the edges on the other.


For $K\_2$, obviously $1$ graph is needed, for $K\_3$, we have $n = 3$ since each edge must be added separately, and for $K\_4$, we have again $n = 3$ (opposite edges, opposite edges, diagonals).




---


For any graph $G$, is there a way to calculate the minimal number $k$ of graphs $H\_k$ needed to construct $G$, and furthermore a way to explicitly specify each $H\_i$?



Building graphs as unions of disjoint edges
Well, in some sense, there is no known way of doing it effectively for arbitrary graphs. (It is NP complete to determine whether $k=\Delta(G)$ or $k=\Delta(G)+1$.) You are actually interested in the edge chromatic number of a graph. See: 


<http://en.wikipedia.org/wiki/Edge_coloring>


