# What is the minimum number of matchings needed to cover all the edges of a graph?

Given a graph, what is the minimum number of matchings needed such that their union contains all the edges in the graph? Is it related to the degree of the graph?

• "Is it related to the degree of the graph?" Clearly, as the number you're after is trivially greater than or equal to the maximum degree. That's not always enough, though, as for instance odd complete graphs require one more. – Arthur Oct 26 '18 at 5:40

In other words, you're asking about the minimum number of colors needed to color all the edges of a graph $$G$$ so that adjacent edges have different colors. That number is called the "edge chromatic number" or "chromatic index" of $$G$$, and is denoted by the symbol $$\chi'(G)$$.
By Vizing's theorem, $$\Delta(G)\le\chi'(G)\le\Delta(G)+1$$ where $$\Delta(G)$$ is the maximum degree of $$G$$. For example, $$\chi'(K_n)=\Delta(K_n)=n-1$$ for even $$n$$, while $$\chi'(K_n)=\Delta(K_n)+1=n$$ for odd $$n\gt1$$.