Show that if G is a connected simple k-regular graph with k ≥ 2 and χ'(G) = k, then G is Hamiltonian Hi I am really lost on this problem. The notation χ'(G) = k means that the graph has a proper edge coloring of size k. I am only to the point where I know our graph G is comprised of cycles, and has an even number of vertices. If it is K color-able then every vertex has k edges of distinct colors. The edges then must be adjacent to other edges of a different colors incident to a different vertex. I feel intuitively if we follow this pattern we will get a cycle that hits all the vertices. Any insight or help would be very appreciated! Thank you!

After a bit of searching, I've found this graph:

which is a cubic, connected, non-Hamiltonian graph with chromatic index $3$. 
Another counterexample could be also the Barnette-Bosák-Lederberg Graph which is also planar.
No wonder you can't prove it, the claim is false.
I hope this helps $\ddot\smile$
