On the wiki page for edge coloring says the following two things:
- "If the size of a maximum matching in a given graph is small, then many matchings will be needed in order to cover all of the edges of the graph. Expressed more formally, this reasoning implies that if a graph has m edges in total, and if at most β edges may belong to a maximum matching, then every edge coloring of the graph must use at least m/β different colors."
- "For a regular graph of degree $k$ that does not have a perfect matching, this lower bound can be used to show that at least $k + 1$ colors are needed."
Can anyone explain the second point?
It also says that a regular graph has a 1-factorization (decomposition into perfect matchings) if and only if it has chromatic index equal to $\Delta(G)$. I understand the forward direction (the decomposition gives you the colouring), but why is the reverse implication true?