Planar Graphs and Graph Coloring

Section 5.2 Planar Graphs and Graph Coloring

Motivating Questions.

In this section, we will explore the following questions.

What does it mean for a graph to be planar? Are all graphs planar?
What does it mean to color a graph’s vertices? How can vertex coloring be used to solve applied problems?
What does the four color theorem say?

Subsection 5.2.1 Planar Graphs

Exploration 5.2.1.

Suppose there are three houses, each needing to be connected to three utilities: water, natural gas, and electricity, as pictured in Figure 5.2.2. For safety reasons, we wish to draw the lines connecting the utilities to the houses so that they do not cross. Can you find an arrangement of utility lines that do not cross?

Figure 5.2.2. Three utilities and three houses.

Exploration 5.2.3.

Suppose there are five train stations, each wishing to be directly connected to the other four without having to pass underneath or over another rail line (no bridges or tunnels). However, the rail lines do not need to be straight, nor do they need to take the shortest path. Can you find a way to draw them so that they do not cross?

The two graphs you drew above are famous and have special names: the first is the complete bipartite graph \(K_{3,3}\), because you can group the vertices into two parts (“bi-partite”) such that every vertex from one group is connected to every vertex in the other. The second is called the complete graph on five vertices, \(K_5\), because it contains all possible edges connecting the vertices.

Activity 5.2.5.

Find at least two different drawings each of the graphs \(K_{3,3}\) and \(K_5\text{.}\) If possible, try to find drawings of the graphs which solve the original problems. Note that your different drawings still describe the same connections.

Definition 5.2.6.

A graph is called planar if it is possible to draw the graph in such a way that none of the edges cross.

Exploration 5.2.7.

Consider the graphs below. For each graph, determine whether it is planar. If so, draw it so none of the edges cross. If not, explain why not.

Thus, the utilities and train station problems can be stated as follows: Are \(K_{3,3}\) or \(K_5\) planar? The answer comes from a theorem of Kuratowski.

Theorem 5.2.9.

A graph is planar if and only if it does not contain a copy of \(K_{3,3}\) or \(K_5\text{,}\) or a subdivision of \(K_{3,3}\) or \(K_5\text{.}\)

Exploration 5.2.10.

To see what we mean by “subdivision”, is the following graph planar?

Subsection 5.2.2 Graph Coloring

Another application of planar graphs arises when deciding how to color a map. A useful coloring must not color states that share a common border (that is, a part of their boundary) with the same color (otherwise it’s difficult to tell where one starts and another begins!). However, an efficient mapmaker might wonder how many colors are needed to color any world map so that no countries which share a border are given the same color.

Exploration 5.2.12.

Consider the blank map of the USA

./usa_map.pdf

displayed in Figure 5.2.13. How many different colors are needed in order to color the states so that no states that share a border are given the same color? How could we model this problem with a graph?

Theorem 5.2.14. Four Color Theorem.

Four colors suffice to color any map such that any two countries which share a part of a border are given different colors.

The proof was very controversial, as it involves the use of computers to check thousands of cases. The proof is generally accepted now, however.

We can use graphs to model maps. The graph in Figure 5.2.16 models the borders found in the generic map shown in Figure 5.2.15.

Question 5.2.17.

Why must the graph associated to a map be planar? Why must it have no loops or multiple edges?

Lest you think graph coloring is just a fun game, consider the following version of a very real situation.

Activity 5.2.18.

Suppose your friendly local university is looking to schedule its final exams. Obviously, it can’t schedule them so that someone in two different classes is scheduled for an exam at the same time. But how many times are actually required?

First, make up a list of at least 5 courses, and 10 students who are in some of these courses. Ensure that each course shares at least one student in common with at least two other courses (this is just to make the problem sufficiently interesting).
Create a graph whose vertices are the courses. Draw an edge between any pair of courses for which a student is enrolled in both courses.
How many colors are required to color the vertices so that no pair of adjacent vertices gets the same color? Can the answer be more than 4? Why or why not?
How many final exam timeslots are required?

In this section, we explored notions of planarity and graph coloring. Planar graphs are useful when modeling connections formed by, e.g., the boundaries on a map. Graph coloring is a helpful concept when needing to partition our vertex sets into unrelated parts (given by the colors).

Exercises 5.2.3 Exercises

1.

Determine the smallest number of colors required to color the graph in Figure 5.2.16.

2.

As we discussed above, the utilities problem is not solvable on a flat sheet of paper (i.e., in the plane). Is it solvable on another surface (e.g., a sphere? maybe something else?). Draw some examples to see if you can find a solution. If you run stuck, do some research online to see if you can find a solution.

3.

A cycle on \(n\) vertices, denoted \(C_n\text{,}\) is the graph with vertex set \(V = \set{v_1, v_2, v_3, \ldots, v_n}\) and edge set \(E = \set{v_1 v_2, v_2 v_3, \ldots, v_{n-1} v_n, v_n v_1}\text{.}\) Draw examples of \(C_n\) for \(n = 3, 4, 5, 6\text{,}\) and then calculate the fewest number of colors needed to color the vertices of a cycle for those graphs. Make a conjecture about what might be true in general and be ready to explain your thinking.

Prev Top Next