Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

Timothy Gowers discusses one such example 7:10 out in this clip and it continues in part 6.

Summary: You have seven candidates and eight papers. Each candidate takes either two or three papers and cannot take two at the same time. Can this be done in three sittings? Form a graph with eight nodes, each representing a paper, and draw an edge between two nodes if they cannot be performed in the same sitting (i.e. at least one student is doing both papers). Then three sittings will be sufficient if and only if there exists a coloring of the graph with three colors such that no two nodes of the same color are connected by an edge.

share|cite|improve this answer
+1. As I commented before, I like this example, but I don't want to accept an answer now because I would like to see some additional examples. – Dennis Gulko Jun 12 '12 at 14:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.