# An edge coloring problem for class two graphs

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.

• This is a homework level question, please try math.stackexchange.com, as this site is for researchers. Commented Sep 26, 2021 at 15:21

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.