Mapmakers in the fictional land of Euleria have drawn the borders of the various dukedoms of the land. To make the map pretty, they wish to color each region. Adjacent regions must be colored differently, but it is perfectly fine to color two distant regions with the same color. What is the fewest colors the mapmakers can use and still accomplish this task?
How many colors do you need to color the faces of a cube so that no two faces that share an edge are colored the same? Is there a polyhedron that would require four colors to do this? Is there a polyhedron that requires five?
Perhaps the most famous graph theory problem is how to color maps.
Given any map of countries, states, counties, etc., how many colors are needed to color each region on the map so that neighboring regions are colored differently?
Actual map makers usually use around seven colors. For one thing, they require watery regions to be a specific color, and with a lot of colors it is easier to find a permissible coloring. We want to know whether there is a smaller palette that will work for any map.
How is this related to graph theory? Well, if we place a vertex in the center of each region (say in the capital of each state) and then connect two vertices if their states share a border, we get a graph. Coloring regions on the map corresponds to coloring the vertices of the graph. Since neighboring regions cannot be colored the same, our graph cannot have vertices colored the same when those vertices are adjacent.
In general, given any graph \(G\text{,}\) a coloring of the vertices with \(k\) colors is called a \(k\)-coloring. If the coloring has the property that adjacent vertices are colored differently, then the coloring is called proper. Every graph has a proper \(k\)-coloring for some \(k\text{.}\) For example, you could color every vertex with a different color. But often you can do better. The smallest \(k\) for which there is a proper \(k\)-coloring is called the chromatic number of the graph, written \(\chi(G)\).
Find the chromatic number of the graphs below.
The graph on the left is \(K_6\text{.}\) The only way to properly color the graph is to give every vertex a different color (since every vertex is adjacent to every other vertex). Thus the chromatic number is 6.
The middle graph can be properly colored with just 3 colors (Red, Blue, and Green). For example:
There is no way to color it with just two colors, since there are three vertices mutually adjacent (i.e., a triangle). Thus the chromatic number is 3.
The graph on the right is just \(K_{2,3}\text{.}\) As with all bipartite graphs, this graph has chromatic number 2: color the vertices on the top row red and the vertices on the bottom row blue.
It appears that there is no limit to how large chromatic numbers can get; the graph \(K_n\) has chromatic number \(n\text{.}\) So how could there possibly be an answer to the original map coloring question? If the chromatic number of graph can be arbitrarily large, then it seems like there would be no upper bound to the number of colors needed for any map. But there is.
The key observation is that while it is true that for any number \(n\text{,}\) there is a graph with chromatic number \(n\text{,}\) only some graphs arrive as representations of maps. If you convert a map to a graph, the edges between vertices correspond to borders between the countries. So you should be able to connect vertices in such a way where the edges do not cross. In other words, the graphs representing maps are all planar!
So the question is, what is the largest chromatic number of any planar graph? The answer is the infamous Four Color Theorem.
If \(G\) is a planar graph, then the chromatic number of \(G\) is less than or equal to 4. Thus any map can be properly colored with 4 or fewer colors.
We will not prove this theorem. Really. Even though the theorem is easy to state and understand, the proof is not. In fact, there is currently no “easy” known proof of the theorem. The current best proof still requires powerful computers to check an unavoidable set of 633 reducible configurations. The idea is that every graph must contain one of these reducible configurations (this fact also needs to be checked by a computer) and that reducible configurations can, in fact, be colored in 4 or fewer colors.
Of course if every planar graph has chromatic number at most 4, then every graph has chromatic number no more than 6. Proving this (even without using the 4 color theorem) is not very difficult, and this at least shows that the chromatic numbers for planar graphs is bounded.
Prove that every planar graph can be properly vertex colored with 6 or fewer colors.
You will want to use a proof by induction on the number of vertices. Use the fact that every planar graph has at least one vertex of degree at most 5.
In 1879, Alfred Kempe published a proof of the Four Color Theorem. It wasn't until 11 years later that Percy John Heawood found an error in the proof. However, the failed proof did lead to a nice proof that every planar graph has chromatic number at most five. The next activity walks you through that proof.
We will prove the Five Color Theorem, that every planar graph has a proper vertex coloring using five (or fewer) colors. We proceed by induction on the number of vertices. So assume that \(G\) is a planar graph with \(n\) vertices, and all planar graphs with fewer vertices have a proper 5-coloring. We will use \(\{1,2,3,4,5\}\) as our set of colors.
Let \(v\) be a vertex of degree five or less (why can we do this?). Let \(H\) be the graph resulting from deleting \(v\) and all its incident edges. What can you say about \(H\text{?}\)
Let \(v_1, v_2, v_3, v_4, v_5\) be the vertices adjacent to \(v\) in \(G\text{.}\) Why is it okay to assume there really are five and further that these five vertices are colored distinctly from each other?
If not, what could we do with \(v\text{?}\)
Assume \(v_1, \ldots, v_5\) are drawn in the plane in clockwise order around \(v\text{,}\) and further that they are colored \(1,2,3,4,5\) respectively. Now consider the induced subgraph \(H_{1,3}\) of \(H\) consisting of all vertices colored 1 and 3 (and their edges). Why can we assume that there is a path from \(v_1\) to \(v_3\) contained in \(H_{1,3}\text{?}\)
If not, what would happen if we recolor \(v_1\) with color 3, and all its adjacent vertices in \(H_{1,3}\) with color 1 and so on? That is, could we swap colors to free up color 1 for \(v\text{?}\)
Now consider \(H_{2,4}\text{,}\) the induced subgraph of \(H\) of vertices colored 2 and 4. Explain why their cannot be a path connecting \(v_2\) and \(v_4\text{,}\) and why this completes the proof.
Remember where \(v_2\) and \(v_4\) are relative to the path connecting \(v_1\) and \(v_3\text{.}\)
You will notice that the proof above doesn't ever use \(v_5\text{,}\) so it is tempting to apply this same technique to prove the four color theorem. See if you can find the error in doing so in fewer than 11 years.
There are plenty of reasons to color graphs other than cartography.
The math department plans to offer 10 classes next semester. Some classes cannot run at the same time (perhaps they are taught by the same professor, or are required for seniors).
| Class: | Conflicts with: |
| A | D I |
| B | D I J |
| C | E F I |
| D | A B F |
| E | H I |
| F | I |
| G | J |
| H | E I J |
| I | A B C E F H |
| J | B G H |
How many different time slots are needed to teach these classes (and which should be taught at the same time)? More importantly, how could we use graph coloring to answer this question?
Radio stations broadcast their signal at certain frequencies. However, there are a limited number of frequencies to choose from, so nationwide many stations use the same frequency. This works because the stations are far enough apart that their signals will not interfere; no one radio could pick them up at the same time.
Suppose 10 new radio stations are to be set up in a currently unpopulated (by radio stations) region. The radio stations that are close enough to each other to cause interference are recorded in the table below. What is the fewest number of frequencies the stations could use.
In the example above, the chromatic number was 5, but this is not a counterexample to the Four Color Theorem, since the graph representing the radio stations is not planar. It would be nice to have some quick way to find the chromatic number of a (possibly non-planar) graph. It turns out nobody knows whether an efficient algorithm for computing chromatic numbers exists.
While we might not be able to find the exact chromatic number of graph easily, we can often give a reasonable range for the chromatic number. In other words, we can give upper and lower bounds for chromatic number.
This is actually not very difficult: for every graph \(G\text{,}\) the chromatic number of \(G\) is at least 1 and at most the number of vertices of \(G\text{.}\)
What? You want better bounds on the chromatic number? Well, let's see what we can do.
Find the chromatic number of the graph below. How do you know the chromatic number is not larger or smaller than your answer?
If you find a proper \(5\)-coloring, could the chromatic number be more than \(5\text{?}\) Could it be less than \(5\text{?}\) What if you found a subgraph that you were sure had chromatic number \(5\text{?}\)
For any graph \(G\text{,}\) if \(H\) is a subgraph with chromatic number \(k\text{,}\) what can you say about the chromatic number of \(G\text{?}\)
Define the clique number of a graph to be the largest \(n\) for which the graph contains a copy of \(K_n\) as a subgraph (a clique in a graph is a set of vertices that are pairwise adjacent, so a copy of \(K_n\) for some \(n\)). State and prove a theorem relating the clique number and the chromatic number of a graph.
Could it be that the only way for a graph to have chromatic number \(n\) is for it to contain an \(n\)-clique?
Find a graph that has chromatic number 3 even though it does not contain \(K_3\) as a subgraph.
Find a graph that has chromatic number 4 even though it does not contain \(K_4\) as a subgraph.
Modify your \(K_3\)-free graph with chromatic number 3.
Challenge: Find a graph that has chromatic number 4 even though it does not contain \(K_3\) as a subgraph.
The smallest such graph contains 11 vertices. Try starting with \(C_5\) and adding vertices creating a lot of odd cycles.
Graphs that do not contain \(K_3\) are called triangle-free. In 1955, Jan Mycielski gave a construction which when applied to any triangle-free graph with chromatic number \(n\) produced a triangle-free graph with chromatic number \(n+1\) (the resulting graph is called the Mycielskian of the original graph). This proves that the there are graphs without even \(K_3\) that have arbitrarily high chromatic number, so the difference between the clique number and chromatic number can be arbitrarily large.
There are times when the chromatic number of \(G\) is equal to the clique number. These graphs have a special name; they are called perfect (actually for a graph to be perfect, every induced subgraph must have this property). If you know that a graph is perfect, then finding the chromatic number is simply a matter of searching for the largest clique. 5 There are special classes of graphs which can be proved to be perfect. One such class is the set of chordal graphs, which have the property that every cycle in the graph contains a chord—an edge between two vertices of the cycle which are not adjacent in the cycle. However, not all graphs are perfect, and searching for the largest clique isn't always easy anyway.
What about an upper bound? For planar graphs, \(\chi(G) \le 4\text{.}\) Also, if a graph has a proper \(k\)-coloring, then \(\chi(G) \le k\text{,}\) but this requires attempting a coloring first. Can we do better? It is helpful to recall our attempts to prove the 6- and 5-color theorems.
Let \(G\) be any graph and let \(v\) be a vertex with degree \(k\text{.}\) Let \(H = G - v\) be the subgraph resulting from removing \(v\) and all its incident edges.
Suppose \(\chi(H) \lt k\text{.}\) What can you conclude about \(\chi(G)\text{?}\)
How many colors would you need to properly color the neighbors of \(v\text{?}\)
Some notation will come in handy. For a vertex \(v\text{,}\) write \(d(v)\) for the degree of \(v\) (i.e., the number of vertices incident to it). We write \(\Delta(G)\) for the maximum degree of \(G\), which is \(\Delta(G) = \max\{d(v) \st v \in G\}\text{.}\)
Prove that for any graph \(G\text{,}\) the chromatic number is no more than one more than the maximum degree. That is, \(\chi(G) \le \Delta(G) + 1\text{.}\)
You could try a proof by induction, or more simply, just try coloring the graph in a greedy way.
There are graphs for which \(\chi(G) = \Delta(G) + 1\text{.}\) For example, \(G\) might be an odd cycle, which has \(\Delta(G) = 2\) but \(\chi(G) = 3\text{.}\) Also note that \(\Delta(K_n) = n-1\) but \(\chi(K_n) = n\text{.}\)
Surprisingly, for connected graphs, these are the only examples of this.
Any connected graph \(G\) satisfies \(\chi(G) \le \Delta(G)\text{,}\) unless \(G\) is a complete graph or an odd cycle, in which case \(\chi(G) = \Delta(G) + 1\text{.}\)
The proof of this theorem is a little tricky. We will be content with the following special case.
Prove by induction on vertices that any graph \(G\) which contains at least one vertex of degree less than \(\Delta(G)\) (the maximal degree of all vertices in \(G\)) has chromatic number at most \(\Delta(G)\text{.}\)
The chromatic number of a graph tells us about coloring vertices, but we could also ask about coloring edges. Just like with vertex coloring, we might insist that edges that are adjacent must be colored differently. Here, we are thinking of two edges as being adjacent if they are incident to the same vertex. The least number of colors required to properly color the edges of a graph \(G\) is called the chromatic index of \(G\text{,}\) written \(\chi'(G)\).
Six friends decide to spend the afternoon playing chess. Everyone will play everyone else once. They have plenty of chess sets but nobody wants to play more than one game at a time. Games will last an hour (thanks to their handy chess clocks). How many hours will the tournament last?
Interestingly, if one of the friends in the above example left, the remaining 5 chess-letes would still need 5 hours: the chromatic index of \(K_5\) is also 5.
In general, what can we say about chromatic index? Certainly \(\chi'(G) \ge \Delta(G)\text{.}\) But how much higher could it be? Only a little higher.
For any graph \(G\text{,}\) the chromatic index \(\chi'(G)\) is either \(\Delta(G)\) or \(\Delta(G) + 1\text{.}\)
At first this theorem makes it seem like chromatic index might not be very interesting. However, deciding which case a graph is in is not always easy. Graphs for which \(\chi'(G) = \Delta(G)\) are called class 1, while the others are called class 2. Bipartite graphs always satisfy \(\chi'(G) = \Delta(G)\text{,}\) so are class 1 (this was proved by König in 1916, decades before Vizing proved his theorem in 1964). In 1965 Vizing proved that all planar graphs with \(\Delta(G) \ge 8\) are of class 1, but this does not hold for all planar graphs with \(2 \le \Delta(G) \le 5\text{.}\) Vizing conjectured that all planar graphs with \(\Delta(G) = 6\) or \(\Delta(G) = 7\) are class 1; the \(\Delta(G) = 7\) case was proved in 2001 by Sanders and Zhao; the \(\Delta(G) = 6\) case is still open.
There is another interesting way we might consider coloring edges, quite different from what we have discussed so far. What if we colored every edge of a graph either red or blue. Can we do so without, say, creating a monochromatic triangle (i.e., an all red or all blue triangle)? Certainly for some graphs the answer is yes.
Find the largest number \(n\) so that there is a 2-coloring of the edges of \(K_n\) with no monochromatic triangle. Prove your answer is correct. This will involve proving that for any 2-coloring of the edges of \(K_{n+1}\text{,}\) there is a monochromatic triangle.
More generally, we can ask for the smallest number \(R = R(m,n)\) such that no matter how we color the edges of \(K_R\) using red and blue, there will either be a red copy of \(K_m\) or a blue copy of \(K_n\text{.}\) The number \(R(m,n)\) is called a Ramsey number. The previous activity proves that \(R(3,3) = 6\text{.}\)
Show that among ten people, there are either four mutual acquaintances or three mutual strangers. What does this say about \(R(4,3)\text{?}\)
Find a way to color the edges of \(K_8\) with red and blue so that there is no red \(K_4\) and no blue \(K_3\text{.}\)
Often when there is a counter-example, there is one with a good deal of symmetry. (Caution: there is a difference between often and always!) One way to help yourself get a symmetric example, if there is one, is to put 8 vertices into a circle. Then, perhaps, you might draw green edges in some sort of regular fashion until it is impossible to draw another green edge between any two of the vertices without creating a green triangle.
Find \(R(4,3)\text{.}\)
All that is left is to decide what can happen with \(K_9\text{.}\) First explain why no matter how the edges are colored red and blue, there is at least one vertex incident to an even number of red edges and an even number of blue edges. What could this even number of red edges be?
At this point you might wonder whether \(R(m,n)\) even exists for all \(m\) and \(n\text{.}\) One way to prove this is to give a bound for it.
Prove that \(R(m,n)\le R(m-1,n) + R(m,n-1)\text{.}\)
What you need to show is that if there are \(R(m - 1, n) + R(m, n - 1)\) people in a room, then there are either \(m\) mutual acquaintances or \(n\) mutual strangers. As with earlier problems, it helps to start with a person and think about the number of people with whom this person is acquainted or nonacquainted. The generalized pigeonhole principle tells you something about these numbers.
What does the equation in Activity 52 tell us about \(R(4,4)\text{?}\)
Consider 17 people arranged in a circle such that each person is acquainted with the first, second, fourth, and eighth person to the right and the first, second, fourth, and eighth person to the left. can you find a set of four mutual acquaintances? Can you find a set of four mutual strangers?
If you could find four mutual acquaintances, you could assume person 1 is among them. And by the generalized pigeonhole principle and symmetry, so are two of the people to the first, second, fourth and eighth to the right. Now there are lots of possibilities for that fourth person. You now have the hard work of using symmetry and the definition of who is acquainted with whom to eliminate all possible combinations of four people. Then you have to think about non-acquaintances.
What is \(R(4,4)\text{?}\)
It turns out that \(R(4,4) = 18\) and \(R(5, 4) = R(4,5) = 25\text{.}\) Beyond that, not much is known. For example, \(R(5,5)\) is at least 43 and at most 48. The gaps get larger as \(m\) and \(n\) increase: \(R(10,10)\) is at least 798 and no more than 23556.
We can also color the edges with more colors. For example, \(R(3,3,3) = 17\text{,}\) which says that if you color the edges of \(K_{17}\) red, blue and green, there is guaranteed to be a monochromatic triangle in one of these colors.