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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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.