Bound for edge chromatic number given size of maximum matching Problem: A maximum matching in $G$ contains $m$ edges. Show that $\chi(G)\geq \frac{|E(G)|}{m}$, where $\chi$ denotes the minimum number of edge coloring.
I know that each edge must be assigned a colour. Since assigning colors to a graph corresponds  to a graph matching, the number of colors assigned must be less than or equal to $m$ by assumption.
But i'm not sure how to proceed.I am aware that this requires a combinatorial argument, but since I have not taken an official course in combinatorics and my experience with it is almost zero, please explain your argument in detail.
 A: Pick a coloring using $\chi (G)$ color, then
$$E(G)=\sum _{i=1}^{\chi (G)}\text{# of edges colored with color }i.$$
Notice now that the edges colored with one color form a matching on the graph, but this quantity is bounded by $m,$ so
$$E(G)=\sum _{i=1}^{\chi (G)}\text{# of edges colored with color }i\leq m\cdot \chi (G).$$
A: Let $M$ be a matching such that $|M| = m$ and consider a minimal partition of edge set $$E(G) = M_1 \cup M_2 \cup ... \cup M_{k-1} \cup M$$
where each $M_i$ is a matching. In other words, we are partitioning the edge set of $G$ into matchings (note that there is no unique way to do such thing but there is a way always). Then, we know that $|M_i| \le m,\ \forall i \in \{1,2,...,k-1\}$. Thus, we can see that $|E(G)| \le mk$ since matchings $M_i$ and $M$ have no edges in common and $|M_i| \le m$, $|M| = m$. Therefore, $k \ge \frac{|E(G)|}{m}$. Here, since the matchings have no edges in common, it is clear that $\chi(G) \le k$. So, we must show that $\chi(G) = k$.
Suppose for a contradiction that $\chi(G) < k$. Then, by Pigeonhole Principle, at least two elements of $\{M_1, M_2, ..., M_{k-1}, M\}$ have the same colors for their edges. But then, their union is also a matching (since they are colored the same color, there is no two adjacent edges in their union). But then we obtained a matching partition of $k-1$ elements, contradicting the minimality of our first matching partition.
