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😊


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}$

  • $\begingroup$ This is a good answer, but as a matter of style, the proof by contradiction is unnecessary. (You still have a valid proof if you omit the first sentence.) $\endgroup$ – Misha Lavrov Nov 21 '18 at 17:26
  • $\begingroup$ @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}}$? $\endgroup$ – ab123 Nov 21 '18 at 22:04
  • 1
    $\begingroup$ It's just a weird intermediate function that grows slower than any polynomial that's always surprising when it occurs in asymptotic bounds. (Notably, Behrend's construction for 3AP-free sets.) $\endgroup$ – Misha Lavrov Nov 21 '18 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.