Given a connected graph with an odd number of nodes. Let k be the least odd number such that the degree of every node deg(u) <= k. Find a way to color the graph with k colors such that no adjacent nodes have the same color. At least one such coloring always exists.

The solution (I found online) is to Dfs on the graph and you will always find some color that is not taken by nodes adjacent to the current node. Pick the one with minimum index.

The solution works obviously when max degree is even, but not for odd.