We say that $G$ is $∆$-critical if $G$ is connected with $∆(G) = ∆$, $χ'(G) = ∆ + 1$, and $χ'(G − e) < χ'(G)$ for any $e ∈ E(G)$. Prove that if $G$ is $∆$-critical, then $d(x) + d(y) ≥ ∆ + 2$ for any $xy ∈ E(G)$.
Any hints or proofs are greatly appreciated.
On
First, we know that $\chi^\prime(G-e)\leq \Delta$ for any edge $e=xy$. This means there is a proper edge-colouring of $G-e$ using at most $\Delta$ colours. Fix such a colouring.
So suppose $\deg_G(x)+\deg_G(y)\leq\Delta+1$, where $\deg_G(x)$ is the degree in $G$, (which you write as $d(x)$). Why must we then have $\deg_{G-e}(x)+\deg_{G-e}\leq \Delta-1$?
So there is some colour in our fixed colouring of $G-e$ that definitely hasn't been used to colour the edges incident to $x$ or $y$. Why does this imply a contradiction?
Suppose the hypothesis is true and the conclusion is false. So suppose $\chi'(G)=\Delta+1$, $\chi'(G-e) \le \Delta, \forall e \in E(G)$, and there exists some $xy \in E(G)$ such that $d(x)+d(y) \le \Delta+1$. We show it is actually possible to edge color $G$ using at most $\Delta$ colors, which is a contradiction. Observe that since $\chi'(G-xy) \le \Delta$, the edges of $G-xy$ can be colored using at most $\Delta$ colors. Finally, the last remaining edge $xy$ can also be colored using one of the $\Delta$ colors since it is incident to at most $(d(x)-1)+(d(y)-1) \le \Delta-1$ colored edges.