Since n <= 100, I thought backtracking wouldn't be fast enough (not tried). So, only other solution I could think is greedy solution (sort vertices by degree, start coloring from the one with lowest degree). It seems correct to me (altough I can't prove it) but it gives WA. Anybody can show me how to prove or disprove it (Or maybe how to make greedy work, maybe with some change like trying all nodes with the same degree)?