Edge coloring - Prove the chromatic index $\chi' \le 2 \Delta(G) - 1$

Question

I've read this upper-bound in many places and all of them treat it as trivial. However, I am not having ideas for a simple proof and also I don't know if this is duplicate, but I didn't find a proof after searching. How to prove it in a simple way?

Answer 1

A simple greedy algorithm for coloring the edges proves this bound. Order the edges $e_1,\ldots,e_m$ and choose colors $1,2,\ldots,2\Delta(G)-1$. For $i\leftarrow 1$ to $m$, assign $e_i$ the lowest color number possible.

In the worst-case, we have an edge $uv$ with $\deg u=\deg v=\Delta(G)$ and each edge other than $uv$ incident to $u$ or $v$ has already been assigned a color. There are $\Delta(G)-1$ such edges incident to both $u$ and $v$, so the assigned colors sum to at most $2\Delta(G)-2$. However, $uv$ is incident to both $u$ and $v$, so only one more color is needed. It follows that the maximum number of colors used is $2\Delta(G)-1$.