# Euler graph k-coloring (np-completeness proof)

I've been studying np-completeness proofs by reduction, and was wondering whether my approach to the following problem is viable.

Define an Euler graph as a graph that 1) is connected, and 2) has every vertex with even degree.

Input: An Euler graph and an integer $k$. Problem: is the given graph $k-colorable$?

Show that the above is NP-complete.

My attempt: The problem is in NP since, given some solution "certificate" consisting of $k$ sets of vertices (where all vertices in a set are assigned the same colors), the solution can be verified in polynomial time: Just go thru each vertex and ensure that none of its neighboring vertices are contained in the same set as that vertex. Since a vertex can have at most $n - 1$ neighbors (where $n = |V|$), this should take asymtotically $O(n^2)$ time.

Reduction: reduce the general $k-coloring$ (chromatic number) problem (which is known to be NP complete). Here is where I run into some questions...

My initial thinking was that, given an instance of the general $k-coloring$ problem, with a graph $G$ and an integer $k$, we can construct $G'$ and $k'$ by adding a single vertex to $G$, and connecting that vertex to every odd vertex in $G$, while letting $k' = k$. But then I saw this wouldn't work for a 2-vertex tree graph. Letting $k' = k + 1$ is no good either, because this wouldn't work for the graph consisting of the shape of a square with a diagonal segment added to it.

So now I'm thinking, why not just locate every pair of odd-degree vertices in $G$ and connect each pair with a single edge, while letting $k' = k$? Would this reduction work, or are there still cases where this wouldn't work?

• Try to prove that your reduction works to know for sure... – Yuval Filmus Mar 9 '16 at 21:20

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 > 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.