Q2

6.042 at MIT is often taught using recitations. Suppose it happened that 8 recitations were needed, with

two or three staff members running each recitation. The assignment of staff to recitation sections, using

their secret code names, is as follows:

\item R1: Maverick, Goose, Iceman

R2: Maverick, Stinger, Viper

R3: Goose, Merlin

R4: Slider, Stinger, Cougar

R5: Slider, Jester, Viper

R6: Jester, Merlin

R7: Jester, Stinger

R8: Goose, Merlin, Viper

Two recitations can not be held in the same 90-minute time slot if some staff member is assigned to

both recitations. The problem is to determine the minimum number of time slots required to complete

all the recitations.

a) Recast (translate) this problem as a question about coloring the vertices of a particular graph.

b) Draw the graph and explain what the vertices, edges, and colors represent. (One free flow-chart

building application that will work to make such an image is https://draw.io

c) Show a coloring of this graph using the fewest possible colors; prove why no fewer colors will

work.

d) What is the resulting schedule of recitations implied by the coloring?