EXAMPLE 5 Scheduling Examinations

Small State is offering eight courses during its summer session. The table shows with an X which pairs of courses have one or more students in common. Only two air-conditioned lecture halls are available for use at any one time. To design an efficient way to schedule the final examinations, we can represent the information in this table by using a graph, as shown in Figure 3.22a. In the graph, courses are represented by vertices and two courses are joined by an edge if there is any student enrolled in both courses.

101

We are faced with the following graph theory problem: Can we assign labels to the vertices of the graph in such a way that vertices that are joined by an edge get different labels? We think of the labels as the time slots the courses are assigned for final examinations. Traditionally, in graph theory such labels are referred to as colors. In this language, we seek to color the vertices of the graph so that vertices that are joined by an edge get different colors. Such a coloring is called a vertex coloring.

Figure 3.22b shows one way to color the vertices of the graph so that each vertex gets a different color. Note that numbers are being used to represent the different colors. This solution is not very valuable, however, because it means that each course must be given its own time slot.

Can we improve upon eight colors? Note that , and the edges that join them form a complete graph on four vertices. To have the vertices that are joined by an edge colored differently, we must assign , and four different colors because each of these four vertices is joined to the other three (see Figure 3.22c). Thus, any coloring of the graph in Figure 3.22a must use at least four colors. Exactly four colors will do, because the four colors used for , and can be used to color the remaining vertices while ensuring that no two vertices joined by an edge have the same color. The improved coloring in Figure 3.22c was found by trial and error.

The examination graph we have been studying has chromatic number 4; hence, we can schedule the eight examinations in four time slots without a conflict. Notice, however, that the coloring in Figure 3.22c schedules three different courses for the time slot corresponding to color 2. This means that not enough rooms with air conditioning will be available. Is there a way to recolor the graph with four colors so that each of the four colors is used only twice? Figure 3.22d shows that the answer is “yes.”

Thus, we are able to schedule the eight final examinations in four time slots, using only two air-conditioned rooms, and no student will have a conflict under this schedule!

102

What is the chromatic number of the graph shown on the right in Spotlight 3.2 on page 99? Show a coloring using the numbers 1, 2, 3, … as colors that achieve the chromatic number of colors.

A group of companies is coming to campus for job interviews. Different companies may want different numbers of time slots to hold their interviews. In each time slot one student can be interviewed. In the example below, all the companies have requested contiguous time slots for the interviews, but this need not be the case. Due to the fact that classes are going on at the same time, five departmental conference rooms have been made available to the companies to conduct their interviews.

The interviews will follow the school’s regular hourly periods, which start at 9 A.M. and end at 4 P.M. (Companies will be scheduled for continuous interviews during lunch-hour times. Interviews cannot be scheduled beyond the end of the period that starts at 4 P.M. and ends at 5 P.M.)

Look at the list of time blocks that the companies requested (where 1 = 9-10 A.M., … , 8 = 4-5 P.M.). Is it possible to accommodate all the companies that wish to do interviewing in the five rooms available while meeting their desired schedule times?

Problems of this kind seem simple enough, and you should try your hand at solving this particular one, for which a schedule does exist! However, this situation is not simple at all. The following facts are known about problems of this kind.

The moral is surprisingly simple: Scheduling problems are very hard to solve.

However, the situation is not always as hopeless as it might seem. If you look at the list of time requests for the corporations, you will note again that, not surprisingly, each company has requested a contiguous block of times. It turns out that when this condition holds, it is possible to determine whether there is a feasible schedule using an algorithm that works relatively quickly.

Many people perceive mathematics as complex because it often uses strange notations and algebraic symbols. Thus, it may come as a surprise that a problem that is relatively easy to state and understand without complex symbolism eluded solution for about 100 years. When it was finally solved, it set off a “firestorm,” with some saying that it had not truly been solved. More important, many of the ideas that have been developed in the theory of graphs were expanded or developed in the course of trying to prove this “guess.”

When a graph can be drawn on a flat piece of paper so that edges meet only at vertices, we can talk about not only the vertices and edges of the graph, but also about its regions or faces. Such graphs are known as plane graphs. Two examples of plane graphs are shown in the diagram below.

Graph (a) has 6 regions (the area “outside” the graph is counted as one of the 6 regions), 5 of which have 3 sides and 1 of which has 5 sides. Graph (b) has 7 regions, 2 of which have 5 sides and 5 of which have 4 sides. To count the number of sides of a region, imagine that you are a small ant and are following the edges around the region, starting at some vertex . You count edges until you get back to w. Note that for each of these graphs, there is one unbounded (goes off to “infinity”) region, in addition to the other regions. When you color the regions of a plane map, do not forget to assign a color to the unbounded region.

If you think of the regions of a plane graph as being distinct countries on a page that is to appear in an atlas, it would be nice if countries that share a border got different colors so that they can be distinguished. Countries that meet at a vertex, but do not share an edge representing a common border, can be given the same color. It is convenient to use the term map for the regions created by the drawing of a plane graph.

The following provocative question was raised in a letter (1852) from Augustus De Morgan to William Rowan Hamilton that was based on a problem posed to De Morgan by his student Fredrick Guthrie, who heard the question from his brother Francis:

Can the regions of any (plane) map always be colored with four or fewer colors?

A clever approach to proving the “Four Color Conjecture” was suggested by Alfred Kempe. Kempe’s “proof” had a subtle error, which defied detection for many years, showing that proofs in mathematics really depend on the community of mathematicians to guarantee their accuracy. The British mathematician Percy Heawood discovered the error Kempe made. Heawood adapted Kempe’s proof to show correctly that any map can be colored with five or fewer colors. Approximately 100 years elapsed before a proof that the Four Color Conjecture was true was found. This occurred in 1976, but there was a curious loose end: The proof found by Wolfgang Haken and Kenneth Appel required that a computer verify a large collection of “calculations,” which were too numerous to be done by hand.

This proof troubled some philosophers and mathematicians, but it has been widely accepted by the mathematics community. In 1995, Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas found another proof. This proof, while simpler and shorter than the earlier Haken-Appel proof, also required computer calculations too numerous to be checked by “hand.” Though it is possible that some new approach to the Four Color Conjecture will avoid the use of computers, this is not widely thought to be likely. However, human ingenuity sometimes surprises us!