The Edge Coloring

Question

Can someone tell me how to prove : The edge chromatic number of a graph must be at least ∆,where ∆ is the largest vertex degree of the graph???

Thank you for any advice

Answer 1

Suppose (on the contrary) that the edge chromatic number is less than the largest vertex degree, say $d_{max}$. There exists some vertex, say $v$ with degree $d_{max}$ in the graph. Consider all edges of $v$ of $v$. If we colour all $d_{max}$ edges that have $v$ as an end, then we are bound to use at least $d_{max}$ colours, since if we use less than $d_{max}$ colours, at least 2 edges will have the same colour (by Pigeonhole principle). Hence edge chromatic number ( fewest number of colors necessary to color each edge of such that no two edges incident on the same vertex have the same color) is at least $d_{max}$