Question: In this exercise a graph is used to help solve a scheduling problem. Twelve faculty members in a mathematics department serve on the following committees:
- Undergraduate Education: Tenner, Peterson, Kashina, Cohen
- Graduate Education: Gatto, Yang, Cohen, Catoiu
- Colloquium: Sahin, McMurry, Ash
- Library: Cortzen, Tenner, Sahin
- Hiring: Gatto, McMurry, Yang, Peterson
- Personnel: Yang, Wang, Cortzen
The committees must all meet during the first week of classes, but there are only three time slots available. Find a schedule that will allow all faculty members to attend the meetings of all committees on which they serve. To do this, represent each committee as the vertex of a graph, and draw an edge between two vertices if the two committees have a common member. Find a way to color the vertices using only three colors so that no two committees have the same color, and explain how to use the result to schedule the meetings.