A proper edge $k$-coloring of a graph is an assignment of $k$ colors to the edges of the graph so that no two adjacent edges have the same color. The smallest integer $k$ such that $G$ has a proper edge $k$-coloring is the chromatic index of $G$.
Giving a simple graph $G$, the well-known Vizing's theorem tells us that the chromatic index of any simple graph $G$ is either $\Delta(G)$ or $\Delta(G)+1$. In particular, if the chromatic index of a graph $G$ is $\Delta(G)+1$, then we say that $G$ is of class two.
Suppose that $G$ is a graph of class two and $\varphi$ is a proper edge coloring using $\Delta(G)+1$ colors. I wonder whether there always exists an edge $uv$ such that
$\varphi(uv)\cup \{\varphi(e)~|~e~is~an~edge~adjacent~to~uv\}$ covers all of the $\Delta(G)+1$ colors.
I guess the answer is yes, however, cannot find any source supporting this. If anyone knows some relative references or can prove or disprove this, please reply me. Thanks in advance.
Best Answer
Yes!
Let $uv$ be an edge colored by the last color, say $\Delta+1$. If $uv$ is incidence with all colors, then it is the required edge. So the only case is that every edge colored with $\Delta+1$ is not incident with some color in $[\Delta]$, and thus it can be recolored by that color. This results an edge $\Delta$-coloring, a contradiciton.