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.

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

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.

  • $\begingroup$ +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. $\endgroup$ – Dennis Gulko Jun 12 '12 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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