Suppose you have a simple graph $G$ with max degree $\Delta(G)=k-1$ and chromatic index $\chi’(G)=k$. Let $v\in V(G)$ be a vertex incident with edges $a, b\in E(G)$. Can you find an edge $k$-coloring which is proper except for having $a, b$ of the same color? And what if you assume the restriction that $|V(G)|=k$? If the answer is “yes”, how do you prove it? (M. Winter has provided a partial answer).
Suppose you have a simple graph $G$ with max degree $\Delta(G)=k-1$ and chromatic index $\chi’(G)=k$. Let $v\in V(G)$ be a vertex incident with edges $a, b, c\in E(G)$. Can you find an edge $k$-coloring which is proper except for having $a, b, c$ of the same color? And what if you assume the restriction that $|V(G)|=k$? Furthermore, what if $G=K_k$, the complete graph on $k$ vertices? If the answer is “yes”, how do you prove it?
Suppose you have a simple graph $G$ with max degree $\Delta(G)=k-1$ and chromatic index $\chi’(G)=k$. Let $v\in V(G)$ be a vertex incident with edges $a, b\in E(G)$. Can you find an edge $k$-coloring which is proper except for having $a, b$ of the same color? And what if you assume the restriction that $|V(G)|=k$? If the answer is “yes”, how do you prove it? There is a generalization of thisthese questions which I would like to prove, but I guess this is a good starting point.
