[UVA1613] I can't find any solutions online with a proof

#1

UVA1613

Shortened statement

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.

Can someone prove that this solution is correct?

#2

Why isn’t it obvious when the maximum degree is odd?

#3

When the maximum degree is odd = k, let u be a node with such degree. If all friends of u have different colors, then it is impossible to color u.

#4

I assume @SansPapyrus683 assume it was asking for a k+1-coloring instead of a k-coloring.

#5

It’s not. Consider a graph with the following edges and the DFS order (1,2,3,4,5,6,7):

1 2
2 3
3 4
4 5
5 6
3 5
4 6
1 6
1 7

Then you get the coloring (1,2,1,2,3,4,2).

1 Like
#6

However, the conditions of the problem statement ensure that you can repeatedly remove a vertex with degree <k until no vertex is left.

1 Like