Edge chromatic number in terms of maximum degree I need help with that question.
Suppose that G has a perfect matching M such that G\M is bipartite.
Determine χ'(G) in terms of Δ, where χ'(G) is the edge chromatic number (ie the minimum number of colours we need to colour each edge of G such that no 2 adjacent edges have the same colour) and Δ is the maximal degree of G (ie the maximum degree of its vertices). Justify your answer.
I managed to prove earlier that χ'(G) ≤ 2Δ - 1 . Maybe I can try to find a lower bound ?
Thank you.
 A: Vizing's theorem states that all graphs $G$ have $\chi'(G)=\Delta$ or $\chi'(G)=\Delta+1$. The former are called class $1$ graphs and the latter are class $2$ graphs. So $\chi'(G\setminus M)=\Delta - 1$ because removing a perfect matching reduces the degree of every vertex by $1$ and all bipartite graphs are of class $1$.
When we add the matching back in, we increase the degree of every vertex by $1$ and we increase the number of required colors on the edges incident with each vertex by at most $1$. Thus $\chi'(G)\ne \Delta +1$ since the number of required colors is no more than $\Delta$, thus $\chi'(G)=\Delta$.
ALTERNATE PROOF (without Vizing's theorem): Let $\Delta(G)=\Delta$ and observe that $\Delta(G\setminus M)=\Delta -1~$ since removing a perfect matching reduces the degree of every vertex by $1$. Since $G\setminus M$ is bipartite, it is also easily seen that $\chi'(G\setminus M)=\Delta-1$. So when we add $M$ back in, there is some edge incident with a vertex of maximum degree in $G\setminus M$. This edge will force us to require an additional color, thus $\chi(G)=(\Delta-1)+1=\Delta$.
@bof: Thanks for pointing out that Vizing's theorem is unnecessary here.
