# Applications of graph colorings to discrete math

I'm looking for interesting examples of questions in discrete math that can be proved using graph colorings (as, for example existence of a particular division of people into $k$ distinct groups with given conditions, using, in the proof, that an associated graph is $k$-colorable). I need those example for a basic course in discrete math for undergraduates. Thanks in advance for any help.

-
Like 7:10 out in this clip? Part 6 is here. –  M.B. Jun 12 '12 at 11:36
@M.B.: That's a nice one, thanks. –  Dennis Gulko Jun 12 '12 at 11:52