Suppose you're trying to make a final exam schedule for six classes: anthropology 107 (A),
Economics 212 (E), information systems 194 (I), statistics 261 (S), history 201 (H), and geology 101
(G). The graph below shows which classes students have in common: these are connected by edges.
Use graph coloring to find the chromatic number.

Question

Quizplus · Accepted Answer

Using graph coloring, we need to assign colors to each node (class) such that no two adjacent nodes have the same color. Starting with the node with the highest degree (most connections), we can assign a color and work our way through the graph until all nodes have a color. In this case, the node with the highest degree is G (geology 101) with connections to A, S, and H.

We can assign G the color 1 and then move on to its neighbors. A and S are connected, so they must have different colors. We can assign A the color 2 and S the color 3. Now, we move on to H, which is only connected to G, so it can have the same color as G (color 1).

Moving on to the next highest degree node, we have E (Economics 212), which is connected to I and S. We already used color 3 for S, so we need to use a different color for E. We can use color 2 for E and color 4 for I.

Finally, we have one node left, which is H (history 201). H is only connected to G (color 1), so it can have a different color, such as color 5.

Thus, we can color the graph with 4 colors, so the chromatic number is 4. Therefore, the answer is C. The chromatic number is the minimum number of colors needed to color the graph such that no two adjacent vertices have the same color. Using graph coloring, we can see that we need at least 4 colors to properly color this graph. Therefore, the answer is C.

Suppose You're Trying to Make a Final Exam Schedule for Six