KöMaL 2024 B5403

Suppose that the edges of a simple, connected $k$-regular ($k \ge 2$) graph $G$ can be colored with $k$ colors such that the colors of the edges meeting at any given vertex are all different. Prove that if we delete any edge from $G$, the resulting graph will still be connected.