Author:
Amanda Hager
Subject:
Mathematics
Material Type:
Lesson
Level:
Academic Lower Division
Provider:
University of Texas at Austin
Tags:
  • D2S2
  • Mindset
  • License:
    Creative Commons Attribution
    Language:
    English
    Media Formats:
    Text/HTML, Video

    Education Standards

    5.3 Four color theorem

    5.3 Four color theorem

    Overview

    TCCNS CourseMATH 1332: Contemporary Mathematics
    UT Austin CourseM 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

    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.

    Described above

     

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

    map of Utah, Colorado, New Mexico, and Arizona

     

    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.

    left: two colors chosen, third blank. Right: Third region is colored in third color

     

    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.

    left: fourth region touches all three, has no color. Right; fourth region has been colored a fourth color.

     

    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. 

    five region map. outermost region is not touching all other regions.

     

    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.

    left: trying to extend the fifth region to touch the one region that it doesn't touch, ends up subdividing the fourth region. Right, all regions recolors to be good/valid.

     

    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.

    a
    Step 1: Draw a vertex in each region. Step 2: Connect two vertices if the regions share a border. Step 3: delete map.
    Caption

     

    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: 1Saburo Matsumoto, Liberal Arts Mathematics, LibreTexts

    Quiz Questions

    1. Yes
    2. No
    3. Yes
    4. 1
    5. 1

    Question 1

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

    map of 11 counties

    1. Yes
    2. No
    3. Impossible to determine

    Question 2

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

    map of 10 counties

    1. Yes
    2. No
    3. Impossible to determine

    Question 3

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

    map of 13 counties

    1. Yes
    2. No
    3. Impossible to determine

    Question 4

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

    1. 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.
    2. 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.
    3. 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.
    4. 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?

    1. The vertices of any planar graph can be colored with at most four colors so that no two adjacent vertices have the same color.
    2. The edges of any planar graph can be colored with at most four colors so that no two adjacent edges have the same color.
    3. The regions of any planar graph can be colored with four colors so that no two regions have the same color.
    4. 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

    11 region map has been turned into an 11 vertex graph.

    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?

    ten region map

     

    Question 5.3.2

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

    eleven region map

     

    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.

    eleven region map

     

    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.

    wheel graphs with 4, 5, 6, 7, 8, 9 vertices

     

    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?

    complete graph on five vertices

    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.