# Building graphs as unions of disjoint edges

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$?

• Theorem 4.4 of orion.math.iastate.edu/burstein/2003/math314/gt2003decomp.pdf asserts that $K_n$ is decomposable using $n-1$ subgraphs. – Nick Gill Nov 12 '13 at 15:58
• @NickGill, doesn't it only say that when $n$ is even? Consider $n = 3$. – Tom Leinster Nov 12 '13 at 17:50
• @Tom, you're quite right. I forgot to specify that $n$ was even. – Nick Gill Nov 13 '13 at 9:39

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: