Let's draw this graph.

Step $3$: Graph Coloring

To solve the graph coloring problem, we'll use a greedy algorithm to assign colors $($exam days$)$

to each course:

Assign color $1$ to $A.$

Assign color $1$ to $B.$

Assign color $2$ to $C($cannot be $1$ due to $D,G).$

Assign color $2$ to $D($cannot be $1$ due to $A,B).$

Assign color $2$ to $E($cannot be $1$ due to $B,D).$

Assign color $2$ to $F($cannot be $1$ due to $D,E.$

Assign color $3$ to $G($cannot be $1$ due to $D,E,F).$

Assign color $3$ to $H($cannot be $1$ due to $A,B,C.$

Assign color $2$ to I $($cannot be $1$ due to B$,$ D$,$ E$,$ F$).$

Assign color $4$ to $J($cannot be $1$ due to $B,D,E,F,H.$

Assign color $2$ to $K($cannot be $1$ due to $A,C,H).$

Assign color $5$ to $L($cannot be $1$ due to $B,C,D,E,F,G,H,$I.

Step $4$: Schedule the Exams

The color assigned to each course corresponds to the day of the exam. We can map these

colors to specific days of the week. For simplicity, let's assume:

Explanation:

Color $1=$ Monday

Color $2=$ Tuesday

Color $3=$ Wednesday

Color $4=$ Thursday

Color $5=$ Friday

Based on our coloring:

Monday: A$,$ B

Tuesday: C$,$ D$,$ E$,$ F$,$ I, K

Wednesday: $G,H$

Thursday: J

Friday: L

Final Exam Schedule

Monday: A $($Algebra$),$ B $($Biology$)$

Tuesday: C $($Chemistry$),$ D $($Design$),$ E $($Economics$),$ F $($French$),$ I $($Italian$),$ K $($Korean$)$

Wednesday: G $($Government$),$ H $($History$)$

Thursday: J $($Journalism$)$

Friday: L $($Literature$)$ Step $1$: Understand the Problem

We need to schedule $12$ final exams over as few days as possible without any conflicts for the

students. Two exams cannot be scheduled on the same day if they have any students in

common. This problem can be visualized as a graph coloring problem where:

Vertices represent the courses.

Edges connect vertices that represent courses with students in common.

Colors represent different exam days.

Step $2$: Create the Graph

Explanation:

We'll represent the courses $($A$,$ B$,$ C$,$ D$,$ E$,$ F$,$ G$,$ H$,$ I, J$,$ K$,$ L$)$ as vertices and draw edges

between them based on the given table.

From the table:

A connects with $D,H,K$

B connects with D$,$ E$,$ H$,$ I, J$,$ L

C connects with D$,$ G$,$ H$,$ I, K$,$ L

D connects with E$,$ F$,$ G$,$ H$,$ I, J$,$ L

E connects with F$,$ G$,$ H$,$ I, J$,$ L

F connects with $G,H,$I,$J,L$

G connects with H$,$ I, J$,$ L

H connects with I, J$,$ K$,$ L

I connects with J$,$ L

J connects with $L$ Let's draw this graph.

Step $3$: Graph Coloring

To solve the graph coloring problem, we'll use a greedy al This is a scheduling problem that involves graph coloring.

A small college has a summer school session that offers $12$ courses. An $"x"$ on the chart below

shows which courses have students in common. There are time slots available each day

$($Monday$,$ Tuesday, Wednesday, Thursday, Friday, and Saturday$)$ to schedule final exams. The

college wishes to schedule the $12$ final exams over as few days as possible without creating

conflicts for the students scheduled to take them. It is OK to have more than one exam

scheduled on the same day, as long as the courses do not have any students in common, e$.$g$.$

Algebra and Chemistry could both have their final exams on Monday since they do not have any

students in common.

The courses are coded as follows:

A is algebra, B is biology, C is chemistry, D is design, $E$ is economics, $F$ is French, $G$ is

government, $H$ is history, I is Italian, $J$ is journalism, $K$ is Korean, $L$ is literature

Read the instructions on the next page.

Draw a graph below that represents this situation to help you solve the problem.

Vertices represent the courses. Label the vertices with the letter of the courses.

Edges represent courses with students in common. Connect $2$ vertices if the courses they

represent have students in common.

Colors represent

Color the graph to help you determine when to schedule the final exams. Follow the rules for

graph coloring and use as few colors as possible. PLEASE USE COLORS and not the letters or

names of colors.

Draw your graph below and color it$.$ Make sure to label the vertices with the names of the

courses.

Write your final exam schedule $($which courses are taking the exam on which days$),$

according to your graph coloring.