# The Edge Coloring

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

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}$$
• @MishaLavrov thanks for the suggestion, I too think now that the first line is avoidable. Btw, what's so interesting about $e^{\sqrt{\log x}}$? – ab123 Nov 21 '18 at 22:04