Euler graph k-coloring (np-completeness proof)
A major part of proving that a problem is NP-hard by reduction is proving that the reduction works. It's not enough to find some procedure which takes an instance of problem A and transforms it to an instance of problem B; you have to figure out the connection betweens solutions of the one instances and solutions of the other.

In your case, one idea that does work pairs up odd-degree vertices and connects every pair to a new vertex. Now all the degrees are even, and the new graph is $k$-colorable iff the old one is $k$-colorable, assuming $k &gt; 2$. I'll let you figure out why this works.

While this idea is similar to your own idea of connected pairs of odd-degree vertices, your idea is problematic since it is not clear that if the original graph is $k$-colorable then so is the new graph. Indeed, if two vertices that you connected were colored using the same color then you cannot use the same coloring for the new graph. The idea described in the previous paragraph is very similar but doesn't suffer from this shortcoming.