# 5.3 Four color theorem

## Overview

TCCNS Course | MATH 1332: Contemporary Mathematics |

UT Austin Course | M 302: Introduction to Mathematics |

# Introduction

**Suggested Resources and Preparation**

**Materials and Technology**

Methods of coloring are crucial. An assortment of maps of regions will also be of use. Even coloring book pages can be used here, although actual maps will seem more compelling.

**Prerequisite Assumptions**

none

**Overview and Student Objectives**

**Lesson Length**

50 minutes

**Lesson Objectives**

Students will understand that:

- All maps of regions can be colored with at most four colors so that regions that share a border never share a color.
- Only some maps of regions can be colored with three colors so that regions that share a border never share a color.

Students will be able to:

- Determine if a given map is 3-colorable.
- Determine if a given map is 4-colorable.
- Produce 3-colorings and 4-colorings of maps with up to 12 regions.
- Create a graph that represents a map of regions, where vetices correspond to regions and edges correspond to borders.

# Four color theorem

## Terms

A **coloring** of a map consisting of regions is just the assignment of a color to each region of the map.

The coloring is **valid/good** if regions that share a border never have the same color.

The coloring is **invalid/bad** if there are regions that share a border and have the same color.

## Examples

The coloring on the left is invalid because there are two yellow regions that share a border. The coloring on the right is valid.

For a second example, regions that share only a vertex and not an entire border may have the same color.

# Inventing Maps

Can we create a map where we need at least three colors to make a "good" coloring? We know that we need to have at least three regions. If all three regions touch both of the others, then when we choose colors for the first two regions, we know that we must use a third color for the third region.

But can we create a map where we need at least four colors to make a good coloring? Suppose we use our previous three-color map. If there were a fourth region that touched all three of the previous regions, we know that we'd have to use a fourth color on it.

But can we create a map where we need at least five colors to make a good coloring? If we simply surround the other four regions, we can use the third color.

If we attempt to force our fifth region to share a border with that center region, we wind up cutting off another region that we can recolor to be a good coloring.

The reality is that it can't be done. You can't invent a map that *requires* five colors for a good coloring.

# The Four Color Theorem

Given a map consisting of connected regions printed on a sheet of paper, the regions can always be colored using only four different colors so that any two regions sharing a border have different colors.

This was one of the first theorems to be proved by a computer, using a proof by exhaustion. In proof by exhaustion, the conclusion is established by dividing it into cases and proving each one separately. The number of cases sometimes may be very large. For example, the first proof of the Four-Color Theorem was a proof by exhaustion with 1,936 cases (in 1976). This proof was controversial because most of the cases were checked by a computer program, not by traditional mathematical arguments. The shortest known proof of the Four-Color Theorem today still has over 600 cases.^{1}

# Graphs that correspond to maps

When we want to solve problems involving maps, it's helpful to convert your map into a graph with vertices and edges. Then you have all of graph theory at your disposal to help you solve your problem.

To convert your map into a graph, let's have regions correspond to vertices. That means you should draw a vertex in every region. Then two vertices will have an edge between them if the two regions share a border.

Every map will correspond to a *planar* graph, meaning no edges intersect each other. This means that the Four Color Theorem can be stated for graphs.

# The Four Color Theorem for Planar Graphs

The vertices of any planar graph can be colored with at most four colors so that no two adjacent vertices have the same color.

Source: ^{1}Saburo Matsumoto, Liberal Arts Mathematics, LibreTexts

# Quiz Questions

- Yes
- No
- Yes
- 1
- 1

# Question 1

Is there a valid coloring of this map with only three colors?

- Yes
- No
- Impossible to determine

# Question 2

Is there a valid coloring of this map with only three colors?

- Yes
- No
- Impossible to determine

# Question 3

Is there a valid coloring of this map with only **four** colors?

- Yes
- No
- Impossible to determine

# Question 4

Which of the following is a correct statement of the Four Color Theorem for maps?

- Given a map consisting of connected regions printed on a sheet of paper, the regions can always be colored using only four different colors so that any two regions sharing a border have different colors.
- Given a map consisting of connected regions, the regions can always be colored using less than four different colors so that any two regions sharing a border have a different color.
- Given a map consisting of connected regions. the borders of the regions can always be colored using four different colors so that every border has a different color.
- Given a map consisting of connected regions, the borders of the regions can always be colored using four colors or fewer so that borders that are next to each other have different colors.

# Question 5

Which of the following is a correct statement of the Four Color Theorem for graphs?

- The vertices of any planar graph can be colored with at most four colors so that no two adjacent vertices have the same color.
- The edges of any planar graph can be colored with at most four colors so that no two adjacent edges have the same color.
- The regions of any planar graph can be colored with four colors so that no two regions have the same color.
- The vertices of any planar graph can be colored with less than four colors so that no two vertices have the same color.

# Homework Questions

# Question 5.3.1

No. If you pick two neighboring regions and color them with different colors, the colors of all but one of the remaining regions will be determined. The last region will border regions of all three colors, so a fourth color must be used.

# Question 5.3.2

Yes. In general, students should be displaying colorings; we haven't studied theorems which guarantee the existence of a three-coloring without directly constructing it.

# Question 5.3.3

# Question 5.3.4

The graph is three-colorable if and only if the number of vertices in the cycle is even. That is because if the center vertex is color 1, then the cycle vertices must alternate between colors 2 and 3.

# Question 5.3.5

Vertices will be children, the colors will be the table number, and two children will be connected with an edge if they should *not* be at the same table/if the vertices should not be the same color. It's tempting to say that it can be done with four tables in this case, but it turns out you can get it done with just two. One possibility is Amalia, Jerivan, Emily, Kassa, and Christian at one table, and Izzy, David, Genesis, Hodor, Brody, and Farhad at the other.

# Question 5.3.6

All vertices are adjacent to all other vertices. This means that you need five different colors to color this graph successfully.

# Question 5.3.7

Reflective writing. Responses vary.

# Question 5.3.1

Can this map be colored with three colors where two regions that share a border cannot have the same color?

# Question 5.3.2

Can this map be colored with three colors where two regions that share a border cannot have the same color?

# Question 5.3.3

Represent this map as a graph, where vertices correspond to regions and two vertices are connected with an edge if the corresponding regions share a border.

# Question 5.3.4

These are wheel graphs. A wheel graph consists of a single vertex which is connected to all vertices of a cycle or loop.

What property of wheel graphs means the graph will be three-colorable? *Remember that when we color graphs we are actually coloring the vertices and not the regions.*

# Question 5.3.5

You are a kindergarten teacher. You need to assign your students to tables. But you know that there are certain students who shouldn't sit together.

- Students: Amalia, Brody, Cristian, David, Emily, Farhad, Genesis, Hodor, Izzy, Jerivan, Kassa, Luisa
- Amalia is always hitting David and Genesis
- Cristian and Farhad talk way too much
- David keeps stealing Jerivan's snacks
- Emily is always tattling on Brody...
- ...and in her defense Brody is nearly always throwing things at Kassa
- Hodor said something about Hodor but really you suspect he was complaining about Amalia and she seems to be really upsetting him
- The last time you let Izzy and Jerivan sit together they poured out entire bottles of glue into their desks and showed, like, zero remorse.

What is the smallest number of tables you need for these children? Use graph theory to support and prove your answer.

Hint: Let the vertices correspond to children and draw an edge between two vertices if those children should *not* sit together. Then the colors can represent table numbers.

# Question 5.3.6

The Four Color Theorem applies to planar graphs. What about non-planar graphs? What is the smallest number of colors you need to make a valid coloring of this graph?

# Question 5.3.7

## Background

Of the many math topics that we study, graph theory is generally considered to be the most useful for the greatest number of careers. Airlines, UPS, Amazon, and the military all use graph theory and even research brand new theorems in graph theory to help them do their jobs. Vertices represent cities, warehouses, or bases, edges can represent distances, roads, or costs, and these companies can study questions like "What's the fastest way to get from A to B?" or "What's the cheapest way to get from A to B?"

## Assignment

Your task is to do some internet research to see if graph theory might be useful for you. Think of some future job or career that you would like to have and try to search for uses of graph theory in that career. Your response should include:

- the job or career that you are considering,
- a list of websites that you found interesting in your search,
- a brief description of the way that graph theory is used in that job or career.

If this is proving impossible, then one way you can alter this assignment to consider a career that you think is interesting or want to know more about, even if you don't actually want to do that career. Another piece of advice is that graphs are sometimes referred to as networks in some of these careers.