Prove that the edge coloring number is smaller than or equal to two times the maximum degree Let G be a graph with maximum degree ∆(G) and χ’(G) the edge coloring number. Prove that χ’(G) ≤ 2∆(G) without using Vizing's theorem.
I really don't have a clue on how to tackle this problem. Can anybody push me in the right direction? Thanks in advance
 A: For any graph G with maximum $\Delta(G)=0, \chi'(G)=0$ and for any graph G with maximum $\Delta(G)=1, \chi'(G)=1$.
Assume as an inductive hypothesis that $\chi'(H) \leq 2\Delta(H)$ for all graphs $H$ with $\Delta(H)<\Delta(G)$ or with $\Delta(H)=\Delta(G)$ and $E(H)<E(G)$.
Now if we remove a vertex of maximum degree $\Delta G$ from G, the remaining graph can be edge-coloured with at most $2\Delta G$ colours by hypothesis. Now the removed vertex and edges can be reinserted as follows: Insert the vertex and chose an edge to reinsert. The connecting vertex has at most $\Delta G-1$ associated colours so we have  $\Delta G+1$ colours to choose from. Inserting a second edge, we have (at most) $\Delta G-1$ colours on the connecting vertex and $1$ colour already chosen from the edge already inserted, so still $\Delta G$ colours to choose from. We can continue adding edges in this way until the last edge when there is at most $\Delta G-1$ colours on the connecting vertex and $\Delta G-1$ colours on the edges already chosen, leaving $2$ colours for the final edge choice, as required.
As you can probably see, this means that, perhaps with a little more work to close out the $\Delta(G)=0$ case, we can actually infer that $\chi'(G) \leq 2\Delta(G)-1$ for $\Delta(G)>0$.
