Skip to ContentGo to accessibility pageKeyboard shortcuts menu
OpenStax Logo
Contemporary Mathematics

12.4 Navigating Graphs

Contemporary Mathematics12.4 Navigating Graphs

Menu
Table of contents
  1. Preface
  2. 1 Sets
    1. Introduction
    2. 1.1 Basic Set Concepts
    3. 1.2 Subsets
    4. 1.3 Understanding Venn Diagrams
    5. 1.4 Set Operations with Two Sets
    6. 1.5 Set Operations with Three Sets
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  3. 2 Logic
    1. Introduction
    2. 2.1 Statements and Quantifiers
    3. 2.2 Compound Statements
    4. 2.3 Constructing Truth Tables
    5. 2.4 Truth Tables for the Conditional and Biconditional
    6. 2.5 Equivalent Statements
    7. 2.6 De Morgan’s Laws
    8. 2.7 Logical Arguments
    9. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Projects
      5. Chapter Review
      6. Chapter Test
  4. 3 Real Number Systems and Number Theory
    1. Introduction
    2. 3.1 Prime and Composite Numbers
    3. 3.2 The Integers
    4. 3.3 Order of Operations
    5. 3.4 Rational Numbers
    6. 3.5 Irrational Numbers
    7. 3.6 Real Numbers
    8. 3.7 Clock Arithmetic
    9. 3.8 Exponents
    10. 3.9 Scientific Notation
    11. 3.10 Arithmetic Sequences
    12. 3.11 Geometric Sequences
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  5. 4 Number Representation and Calculation
    1. Introduction
    2. 4.1 Hindu-Arabic Positional System
    3. 4.2 Early Numeration Systems
    4. 4.3 Converting with Base Systems
    5. 4.4 Addition and Subtraction in Base Systems
    6. 4.5 Multiplication and Division in Base Systems
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Projects
      5. Chapter Review
      6. Chapter Test
  6. 5 Algebra
    1. Introduction
    2. 5.1 Algebraic Expressions
    3. 5.2 Linear Equations in One Variable with Applications
    4. 5.3 Linear Inequalities in One Variable with Applications
    5. 5.4 Ratios and Proportions
    6. 5.5 Graphing Linear Equations and Inequalities
    7. 5.6 Quadratic Equations with Two Variables with Applications
    8. 5.7 Functions
    9. 5.8 Graphing Functions
    10. 5.9 Systems of Linear Equations in Two Variables
    11. 5.10 Systems of Linear Inequalities in Two Variables
    12. 5.11 Linear Programming
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  7. 6 Money Management
    1. Introduction
    2. 6.1 Understanding Percent
    3. 6.2 Discounts, Markups, and Sales Tax
    4. 6.3 Simple Interest
    5. 6.4 Compound Interest
    6. 6.5 Making a Personal Budget
    7. 6.6 Methods of Savings
    8. 6.7 Investments
    9. 6.8 The Basics of Loans
    10. 6.9 Understanding Student Loans
    11. 6.10 Credit Cards
    12. 6.11 Buying or Leasing a Car
    13. 6.12 Renting and Homeownership
    14. 6.13 Income Tax
    15. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  8. 7 Probability
    1. Introduction
    2. 7.1 The Multiplication Rule for Counting
    3. 7.2 Permutations
    4. 7.3 Combinations
    5. 7.4 Tree Diagrams, Tables, and Outcomes
    6. 7.5 Basic Concepts of Probability
    7. 7.6 Probability with Permutations and Combinations
    8. 7.7 What Are the Odds?
    9. 7.8 The Addition Rule for Probability
    10. 7.9 Conditional Probability and the Multiplication Rule
    11. 7.10 The Binomial Distribution
    12. 7.11 Expected Value
    13. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Formula Review
      4. Projects
      5. Chapter Review
      6. Chapter Test
  9. 8 Statistics
    1. Introduction
    2. 8.1 Gathering and Organizing Data
    3. 8.2 Visualizing Data
    4. 8.3 Mean, Median and Mode
    5. 8.4 Range and Standard Deviation
    6. 8.5 Percentiles
    7. 8.6 The Normal Distribution
    8. 8.7 Applications of the Normal Distribution
    9. 8.8 Scatter Plots, Correlation, and Regression Lines
    10. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  10. 9 Metric Measurement
    1. Introduction
    2. 9.1 The Metric System
    3. 9.2 Measuring Area
    4. 9.3 Measuring Volume
    5. 9.4 Measuring Weight
    6. 9.5 Measuring Temperature
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  11. 10 Geometry
    1. Introduction
    2. 10.1 Points, Lines, and Planes
    3. 10.2 Angles
    4. 10.3 Triangles
    5. 10.4 Polygons, Perimeter, and Circumference
    6. 10.5 Tessellations
    7. 10.6 Area
    8. 10.7 Volume and Surface Area
    9. 10.8 Right Triangle Trigonometry
    10. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  12. 11 Voting and Apportionment
    1. Introduction
    2. 11.1 Voting Methods
    3. 11.2 Fairness in Voting Methods
    4. 11.3 Standard Divisors, Standard Quotas, and the Apportionment Problem
    5. 11.4 Apportionment Methods
    6. 11.5 Fairness in Apportionment Methods
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  13. 12 Graph Theory
    1. Introduction
    2. 12.1 Graph Basics
    3. 12.2 Graph Structures
    4. 12.3 Comparing Graphs
    5. 12.4 Navigating Graphs
    6. 12.5 Euler Circuits
    7. 12.6 Euler Trails
    8. 12.7 Hamilton Cycles
    9. 12.8 Hamilton Paths
    10. 12.9 Traveling Salesperson Problem
    11. 12.10 Trees
    12. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Videos
      4. Formula Review
      5. Projects
      6. Chapter Review
      7. Chapter Test
  14. 13 Math and...
    1. Introduction
    2. 13.1 Math and Art
    3. 13.2 Math and the Environment
    4. 13.3 Math and Medicine
    5. 13.4 Math and Music
    6. 13.5 Math and Sports
    7. Chapter Summary
      1. Key Terms
      2. Key Concepts
      3. Formula Review
      4. Projects
      5. Chapter Review
      6. Chapter Test
  15. A | Co-Req Appendix: Integer Powers of 10
  16. Answer Key
    1. Chapter 1
    2. Chapter 2
    3. Chapter 3
    4. Chapter 4
    5. Chapter 5
    6. Chapter 6
    7. Chapter 7
    8. Chapter 8
    9. Chapter 9
    10. Chapter 10
    11. Chapter 11
    12. Chapter 12
    13. Chapter 13
  17. Index
People walking through a maze of hedges.
Figure 12.77 Visitors navigate a garden maze. (credit: “Longleat Maze” by Niki Odolphie/Wikimedia, CC BY 2.0)

Learning Objectives

After completing this section, you should be able to:

  1. Describe and identify walks, trails, paths, and circuits.
  2. Solve application problems using walks, trails, paths, and circuits.
  3. Identify the chromatic number of a graph.
  4. Describe the Four-Color Problem.
  5. Solve applications using graph colorings.

Now that we know the basic parts of graphs and we can distinguish one graph from another, it is time to really put our graphs to work for us. Many applications of graph theory involve navigating through a graph very much like you would navigate through a maze. Imagine that you are at the entrance to a maze. Your goal is to get from one point to another as efficiently as possible. Maybe there are treasures hidden along the way that make straying from the shortest path worthwhile, or maybe you just need to get to the end fast. Either way, you definitely want to avoid any wrong turns that would cause unnecessary backtracking. Luckily, graph theory is here to help!

Walks

Suppose Figure 12.78 is a maze you want to solve. You want to get from the start to the end.

A maze with its start and end labeled.
Figure 12.78 Your Maze

You can approach this task any way you want. The only rule is that you can’t climb over the wall. To put this in the context of graph theory, let’s imagine that at every intersection and every turn, there is a vertex. The edges that join the vertices must stay within the walls. The graph within the maze would look like Figure 12.79.

A maze with its start and end labeled. Vertices are marked at each corner of the maze. A path connects all the vertices of the maze.
Figure 12.79 The Graph in Your Maze

One approach to solving a maze is to just start walking. It is not the most efficient approach. You might cross through the same intersection twice. You might backtrack a bit. It’s okay. We are just out for a walk. It might look something like the black sequence of vertices and edges in Figure 12.80.

A maze with its start and end labeled. Vertices are marked at each corner of the maze. A path connects all the vertices of the maze. The path from start to end is highlighted.
Figure 12.80 The Walk Through the Graph in Your Maze

This type of sequence of adjacent vertices and edges is actually called a walk (or directed walk) in graph theory too!

A walk can be identified by naming the sequence of its vertices (or by naming the sequence of its edges if those are labeled). Let’s take the graph out of the context of the maze and give each vertex a name and each edge of the walk a direction as in Figure 12.81.

A graph with 19 vertices and 19 edges. The vertices are a, l, e, h, m, p, r, q, s, o, n, i, j, k, g, c, d, f, and b. The edges connect l a, a b, b f, e f, e h, h m, r s, p q, c d c j, g k, i j, j k, i n, n o, o q, and k s. The following path is highlighted p, q, o, n, i, j, k, s, and r. p is labeled start and q is labeled end. The edges from j to c and c to d are connected via double-headed arrows.
Figure 12.81 The Graph without Your Maze

The name of this walk from p to r is pqonijcdcjksr. When a particular edge on our graph was traveled in both directions, it had arrows in both directions and the letters of vertices that were visited more than once had to be repeated in the name of the walk.

Checkpoint

Not every list of vertices or list of edges makes a path. The order must take into account the way in which the edges and vertices are connected. The list must be a sequence, which means they are in order. No edges or vertices can be skipped and you cannot go off the graph.

Two graphs are labeled graph X and graph Y. Graph X has six vertices: a, b, c, d, e, and f. The vertices a, b, and e are connected by three edges and it resembles a triangle. The vertices, c, d, and f are connected by three edges and it resembles a triangle. These two triangles overlap and the point where they overlap has no vertex. The edges from b to d and d to f are highlighted. Graph Y is the same as that of graph X. The point where they overlap has a vertex, g.
Figure 12.82 A Walk or Not a Walk?

The highlighted edges Graph Y in Figure 12.82 represent a walk between f and b. The highlighted edges in Graph X do not represent a walk between f and b, because there is a turn at a point that is not a vertex. This is like climbing over a wall when you are walking through a maze. Another way of saying this is that bdf is not a walk, because there is no edge between b and d.

Checkpoint

A point on a graph where two edges cross is not a vertex.

Example 12.19

Naming a Walk Through A House

Figure 12.83 shows the floor plan of a house. Use the floor plan to answer each question.

A floor plan of a house includes the master bedroom, bedroom, kitchen, living room, hallway, garage, and restroom.
Figure 12.83 Floor Plan of a House
  1. Draw a graph to represent the floor plan in which each vertex represents a different room (or hallway) and edges represent doorways between rooms.
  2. Name a walk through the house that begins in the living room, ends in the garage and visits each room (or hallway) at least once.

Your Turn 12.19

1.
Recall from the Graph Basics section that a graph in which there are multiple edges between the same pair of vertices is called a multigraph. The figure shows a map of the four bridges that link Staten Island to Brooklyn and New Jersey and a multigraph representing the map. In the multigraph, the edges are labeled instead of the vertices. The edges represent the bridges, G (Goethals Bridge), B (Bayonne Bridge), C (Outerbridge Crossing), and V (Verrazzano-Narrows Bridge). The vertices represent New Jersey, Staten Island, and Brooklyn.
A map and a graph of Staten Island Bridges. The map of Staten Island shows the following bridges: Bayonne Bridge, Verrazano Bridge, Goethals Bridge, and Outer bridge Crossing. The graph shows three vertices. Three edges from the first vertex lead to B, G, and C. Edges from B, G, and C lead to the second vertex. An edge from the second vertex leads to V. An edge from V leads to the third vertex.
Figure 12.87 Map and Multigraph of Staten Island Bridges
A path can be named by a sequences of edges instead of a sequence of vertices. Determine which of the following sequence of edges is a walk.
  1. BVCGC
  2. VCBGC
  3. CVGBB
  4. GVBVC

Paths and Trails

A walk is the most basic way of navigating a graph because it has no restrictions except staying on the graph. When there are restrictions on which vertices or edges we can visit, we will call the walk by a different name. For example, if we want to find a walk that avoids travelling the same edge twice, we will say we want to find a trail (or directed trail). If we want to find a walk that avoids visiting the same vertex twice, we will say, we want to find a path (or directed path).

Walks, trails, and paths are all related.

  1. All paths are trails, but trails that visit the same vertex twice are not paths.
  2. All trails are walks, but walks in which an edge is visited twice would not be trails.

We can visualize the relationship as in Figure 12.88.

Three concentric ovals represent paths, trails, and walks. The first (inner) oval labeled paths reads, no repeated edges or vertices. The second oval labeled trails reads, no repeated edges. The third oval is labeled walks.
Figure 12.88 Walks, Trails, and Paths

Let’s practice identifying walks, trails, and paths using the graphs in Figure 12.89.

Two graphs are labeled graph A and graph K. Graph A has five vertices: b, c, d, e, and f. The edges connect b c, c f, b d, b e, d e, and e f. Graph K has five vertices: m, n, o, p, and q. The edges connect m n, n o, n q, q o, o p, n p, and m p.
Figure 12.89 Graphs A and K

Example 12.20

Identifying Walks, Paths, and Trails

Consider each sequence of vertices from Graph A in Figure 12.89. Determine if it is only a walk, both a walk and a path, both a walk and a trail, all three, or none of these.

  1. bcdef
  2. cbdbe
  3. cfedbc
  4. befcbd

Your Turn 12.20

Consider each sequence of vertices from Graph K in Figure 12.106. Determine if it is only a walk, both a walk and a path, both a walk and a trail, all three, or none of these.
1.
nqop
2.
pnqonm
3.
mnopq

Circuits

In many applications of graph theory, such as creating efficient delivery routes, beginning and ending at the same location is a requirement. When a walk, path, or trail end at the same location or vertex they began, we call it closed. Otherwise, we call it open (does not begin and end at the same location or vertex). Some examples of closed walks, closed trails, and closed paths are given in in the following table.

DESCRIPTION EXAMPLE CHARACTERISTICS
A closed walk is a walk that begins and ends at the same vertex.
A graph has five vertices: b, c, d, e, and f. All the vertices are interconnected. An arrow labeled 1 flows from d to f. An arrow labeled 2 flows from f to b. An arrow labeled 3 flows from b to c. An arrow labeled 4 flows from c to f. An arrow labeled 5 flows from f to d.

dfbcfd

Alternating sequence of vertices and edges

Begins and ends at the same vertex

A closed trail is a trail that begins and ends at the same vertex. It is commonly called a circuit.
A graph has five vertices b, c, d, e, and f. All the vertices are interconnected. An arrow labeled 1 flows from d to f. An arrow labeled 2 flows from f to b. An arrow labeled 3 flows from b to c. An arrow labeled 4 flows from c to f. An arrow labeled 5 flows from f to e. An arrow labeled 6 flows from e to d.

dfbcfed

No repeated edges

Begins and ends at the same vertex

A closed path is a path that begins and ends at the same vertex. It is also referred to as a directed cycle because it travels through a cyclic subgraph.
A graph has five vertices b, c, d, e, and f. All the vertices are interconnected. An arrow labeled 1 flows from d to f. An arrow labeled 2 flows from f to b. An arrow labeled 3 flows from b to c. An arrow labeled 4 flows from c to d.

dfbcd

No repeated edges or vertices

Begins and ends at the same vertex

Table 12.4 Closed Walks, Trails, and Paths

Since walks, trails, and paths are all related, closed walks, circuits, and directed cycles are related too.

  1. All circuits are closed walks, but closed walks that visit the same edge twice are not circuits.
  2. All directed cycles are circuits, but circuits in which a vertex is visited twice are not directed cycles.

We can visualize the relationship as in Figure 12.94.

Three concentric ovals represent directed cycles, circuits, and closed walks. The first (inner) oval labeled directed cycles (closed paths) reads, no repeated edges or vertices. The second oval labeled circuits (closed talks) reads, no repeated edges. The third oval is labeled closed walks.
Figure 12.94 Closed Walks, Circuits, and Directed Cycles

The same circuit can be named using any of its vertices as a starting point. For example, the circuit dfbcd can also be referred to in the following ways.

abcda is the same as

{ bcdabcdabcdabcd{ bcdabcdabcdabcd

Let’s practice working with closed walks, circuits (closed trails), and directed cycles (closed paths). In the graph in Figure 12.95, the vertices are major central and south Florida airports. The edges are direct flights between them.

A graph represents the direct flights between Central and South Florida airports. The graph has six vertices: T P A, M C O, P B I, F L L, M I A, and E Y W. Edges from T P A lead to E Y W, M I A, F L L, and P B I. Edges from M C O lead to E Y W, M I A, and F L L. An edge from E Y W leads to F L L.
Figure 12.95 Major Central and South Florida Airports

Example 12.21

Determining a Closed Walk, Circuit, or Directed Cycle

Suppose that you need to travel by air from Miami (MIA) to Orlando (MCO) and you were restricted to flights represented on the graph. For the trip to Orlando, you decide to purchase tickets with a layover in Key West (EYW) as shown in Figure 12.96, but you still have to decide on the return trip. Determine if your roundtrip itinerary is a closed walk, a circuit, and/or a directed cycle, based on the return trip described in each part.

A graph represents the direct flights between Central and South Florida airports. The graph has six vertices: T P A, M C O, P B I, F L L, M I A, and E Y W. Edges from T P A lead to E Y W, M I A, F L L, and P B I. Edges from M C O lead to E Y W, M I A, and F L L. An edge from E Y W leads to F L L. An arrow from M I A points to E Y W. An arrow from E Y W points to M C O.
Figure 12.96 MIA to EYW to MCO
  1. You returned to Miami (MIA) by reversing your route.
  2. Your direct flight back left Orlando (MCO) but was diverted to Fort Lauderdale (FLL)! From there you flew to Tampa (TPA) before returning to Miami (MIA).

Your Turn 12.21

Suppose that you want to travel from Palm Beach (PBI) to any other city listed in Figure 12.113 and then return to Palm Beach.
1.
Why is it impossible to find an itinerary that is a circuit?
2.
How is this related to the degree of the vertex PBI?

Graph Colorings

In this section so far, we have looked at how to navigate graphs by proceeding from one vertex to another in a sequence that does not skip any vertices, but in some applications we may want to skip vertices. Remember the camp Olympics at Camp Woebegone in Comparing Graphs? You were planning a camp Olympics with four events. The campers signed up for the events. You drew a graph to help you visualize which events have campers in common. The vertices of Graph E in Figure 12.97 represent the events and adjacent vertices indicate that there are campers who are participating in both.

A graph with four vertices: a, b, c, and d. The edges connect a b, b d, d c, and c a.
Figure 12.97 Graphs of Camp Olympics

In this case, we do NOT want events represented by two adjacent vertices to occur in the same timeslot, because that would prevent the campers who wanted to participate in both from doing so. We can use the graph in Figure 12.97 to count the timeslots we need so there are no conflicts. Let’s assign each timeslot a different color. We could categorize events that happen at 1 pm as Red; 2 pm, Purple; 3 pm, Blue; and 4 pm, Green. Then assign different colors to any pair of adjacent vertices to ensure that the events they represent do not end up in the same timeslot. Figure 12.98 shows several of the ways to do this while obeying the rule that no pair of adjacent vertices can be the same color.

Three graphs are labeled graph 1, graph 2, and graph 3. Graph 1 has four vertices: a, b, c, and d in blue, green, purple, and red, respectively. Graph 2 has four vertices: a, b, c, and d in blue, purple, purple, and red, respectively. Graph 3 has four vertices: a, b, c, and d in red, purple, purple, and red, respectively. In each graph, the edges connect a b, b d, d c, and c a.
Figure 12.98 Graph Colorings

In Figure 12.98, the graphs with vertices colored so that no adjacent vertices are the same color are called graph colorings. Notice that Graph 3 has the fewest colors, which means it shows us how to have the fewest number of timeslots. The events marked in red, a and d, can be held at the same time because they are not adjacent and do not have conflicts. Also, the events marked in purple, b and c, can be held at the same time. We would not need green or blue timeslots at all!

A graph that uses nn colors is called an nn-coloring. The smallest number of colors needed to color a particular graph is called its chromatic number.

Graph colorings can be used in many applications like the scheduling scenario at camp Woebegone. Let's look at how they work in more detail. Figure 12.99 shows two different colorings of a particular graph. Coloring A is called a four-coloring, because it uses four colors, red (R), green (G), blue (B), and purple (P). Coloring B is called a three-coloring because it uses three. The colors allow us to visually subdivide the graphs into groups. The only rule is that adjacent vertices are different colors so that they are in different groups.

Two graphs are labeled coloring A and coloring B In the first graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: B, G, and R. Row 2: G, R, and P. Row 3: P, B, and G. The outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect G R, R B, G R, and R P. Diagonal lines connect B R, R G, G B, and G P. In the second graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: B, G, and R. Row 2: G, R, and B. Row 3: R, B, and G. The outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect G R, R B, G R, and R B. Diagonal lines connect B R, R G, G B, and G B.
Figure 12.99 Two Colorings of the Same Graph

It turns out that a three-coloring is the best we can do with the graph in Figure 12.99. No matter how many different patterns you try with only two colors, you will never find one in which the adjacent vertices are always different colors. In other words, the graph has a chromatic number of three. For large graphs, computer assistance is usually required to find the chromatic numbers. There is no formula for finding the chromatic number of a graph, but there are some facts that are helpful in Table 12.5.

Fact Example
Recall that planar graphs are untangled; that is, they can be drawn on a flat surface so that no two edges are crossing. If a graph is planar, it can be colored with four colors or possibly fewer.
Three graphs. The first graph titled tangled has nine vertices labeled a to i. The edges connect a b, a d, a e, c e, e g, e i, g f, f i, and i h. The second graph titled untangled has nine vertices labeled a to i. The edges connect a b, a d, a e, e c, e g, e i, i h, i f, and g f. The third graph titled 4 or fewer colors has nine vertices a to i in red, green, green, green, blue, blue, green, blue, and red. The edges connect a b, a d, a e, e c, e g, e i, i h, i f, and g f.
Each vertex in a complete graph is adjacent to every other vertex forcing us to color them all different colors.The chromatic number of a complete graph is the same as the number of vertices.
Two graphs. The first graph has five vertices in red, blue, green, yellow, and purple. All vertices are interconnected. Text reads, 5 vertices and 5 colors. The second graph has four vertices in red, blue, green, and purple. All vertices are interconnected. Text reads, 4 vertices, and 4 colors.
If a graph has a clique, a complete subgraph, then each vertex in the clique must have a different color and the vertices outside the clique may or may not have even more colors. The chromatic number of a graph is at least the number of vertices in its biggest clique.
Two graphs. The first graph has five vertices in red, green, purple, green, and red. The edges connect R with G, R with P, G with P, P with second G, and second G with the second R. The three colors, R, G, and P are outlined. The second graph has six vertices in red, blue, green, purple, blue, and red. The first four vertices are interconnected and outlined. Purple is connected with the fifth vertex, blue. The fifth vertex is connected to the sixth vertex, red.
Table 12.5 Facts about Graph Colorings

Creating Colorings to Solve Problems

Let’s see how these facts can help us color the graph in Figure 12.100.

  • Since the graph is planar, the chromatic number is no more than four.
  • The graph is not complete, but it has complete subgraphs of three vertices. In other words, it has triangles like the one shown with blue vertices in Figure 12.100. This means that the chromatic number is at least three.
A graph has nine vertices arranged in 3 rows and 3 columns. The outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect the vertices along the lines. Diagonal lines from top-left to bottom-right connect the vertices along the lines. The vertices at the top-left, left-center, and center are highlighted in grey.
Figure 12.100 A Graph with Triangles

We know we can color this graph in three or four colors. It is usually best to start by coloring the vertex of highest degree as shown in Figure 12.101. In this case, we used red (R). The color is not important.

Two graphs are labeled degrees of vertices and degree 6 vertex colored first. In the first graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, 4, and 2. Row 2: 4, 6, and 4. Row 3: 2, 4, and 3. In the second graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, 4, and 2. Row 3: 4, R, and 4. Row 3: 2, 4, and 3. In each graph, the outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect the vertices along the lines. Diagonal lines from top-left to bottom-right connect the vertices along the lines. An arrow from the first graph points to the second graph.
Figure 12.101 Color Highest Degree Vertex First

We want to color as many of the vertices the same color as possible; so, we look at all the vertices that are not adjacent to the red vertex and begin to color them, red starting with the one among them of highest degree. Since the only vertices that are not adjacent are both degree 2, choose either one and color it red as shown in Figure 12.102.

Two graphs. In the first graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, 4, and 2. Row 3: 4, R, and 4. Row 3: 2, 4, and 3. 2 in the top-right and bottom-left vertices are outlined. In the second graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, 4, and R. Row 2: 4, R, and 4. Row 3: 2, 4, and 3. In each graph, the outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect the vertices along the lines. Diagonal lines from top-left to bottom-right connect the vertices along the lines. An arrow from the first graph points to the second graph.
Figure 12.102 Color More Red from Highest to Lowest Degree

Now, there is only one vertex left that is not adjacent to a red; so, color it red. Of the remaining vertices, the highest degree is four; so, color one of the vertices of degree four in a different color. These two steps are shown in Figure 12.103.

Two graphs. In the first graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, 4, and R. Row 3: 4, R, and 4. Row 3: R, 4, and 3. In the second graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, B, and R. Row 2: 4, R, and 4. Row 3: R, 4, and 3. In each graph, the outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect the vertices along the lines. Diagonal lines from top-left to bottom-right connect the vertices along the lines. An arrow from the first graph points to the second graph.
Figure 12.103 Complete the Reds and Start Another Color

Repeat the same procedure. There are three remaining vertices that are not adjacent to a blue. Color as many blue as possible, with priority going to vertices of higher degree as shown in Figure 12.104.

Three graphs. In the first graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, B, and R. Row 3: 4, R, and 4. Row 3: R, 4, and 3. 4 in the left-center and bottom-center vertices are outlined. 3 in the bottom-right vertex is outlined. In the second graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, B, and R. Row 2: B, R, and 4. Row 3: R, 4, and 3. 3 in the bottom-right vertex is outlined. In the third graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, B, and R. Row 2: B, R, and 4. Row 3: R, 4, and B. In each graph, the outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect the vertices along the lines. Diagonal lines from top-left to bottom-right connect the vertices along the lines. An arrow from the first graph points to the second graph. An arrow from the second graph points to the third graph.
Figure 12.104 Repeat Procedure for Color Blue

All the remaining vertices are adjacent to blue. So, it is time to repeat the procedure with another color as shown in Figure 12.105.

Three graphs. In the first graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, B, and R. Row 3: B, R, and P. Row 3: R, 4, and B. 3 in the top-left vertex is outlined. 4 in the bottom-center is outlined. In the second graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: 3, B, and R. Row 2: B, R, and P. Row 3: R, P, and B. 3 in the top-left vertex is outlined. In the third graph, nine vertices are present. The vertices are arranged in 3 rows and 3 columns. Row 1: P, B, and R. Row 2: B, R, and P. Row 3: R, P, and B. In each graph, the outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect the vertices along the lines. Diagonal lines from top-left to bottom-right connect the vertices along the lines. An arrow from the first graph points to the second graph. An arrow from the second graph points to the third graph.
Figure 12.105 Repeat Procedure for Color Purple

All the vertices are now colored with a three-coloring so we know the chromatic number is at most three, but we knew the chromatic number was at least three because the graph has a triangle. So, we are now certain it is exactly three.

Suppose the vertices of the graph in Figure 12.106 represented the nine events in the Camp Woebegone Olympics, and edges join any events that have campers in common, but nonadjacent vertices do not.

A graph has nine vertices. The vertices are arranged in 3 rows and 3 columns. Row 1: P, B, and R. Row 2: B, R, and P. Row 3: R, P, and B. In each graph, the outer vertices are connected to form a square. A vertical line and a horizontal line at the center connect the vertices along the lines. Diagonal lines from top-left to bottom-right connect the vertices along the lines.
Figure 12.106 Coloring for Nine Event Camp Woebegone Olympics

Any vertices of the same color are nonadjacent; so, they have no conflicts. Since this graph is a three-coloring, all nine events could be scheduled in just three timeslots!

Example 12.22

Understanding Chromatic Numbers

In Example 12.17, we discussed a high school, which holds end-of-course exams in (E3) English 3, (E4) English 4, (M) Advanced Math, (C) Calculus, (W) World History, (U) U.S. History, (B) Biology, and (P) Physics. We were given a list of courses that had no students in common. We used that information to find the graph in Figure 12.71, which shows edges between exams with students in common. Use the graph we found in Example 12.17 to answer each question.

A graph has eight vertices. The vertices are P, B, U, W, C, M, E 4, and E 3. Edges from P lead to E 3, B, U, W, and C. Edges from B lead to U, W, C, M, and E 4. Edges from U lead to E 3, M, and C. Edges from W lead to E 4, M, and C. An edge from C leads to E 3. An edge from M leads to E 3.
Figure 12.107 Graph of Exams with Students in Common
  1. The graph contains a clique of size 4 formed by the vertices P, E3, C, and U. What does this tell you about the chromatic number?
  2. The graph is not planar, meaning that you cannot untangle it. What does this tell you about the chromatic number?
  3. Create a coloring by coloring vertex of highest degree first, coloring as many other vertices as possible each color from highest to lowest degree, then repeating this process for the remaining vertices.
  4. Do you know what the minimum number of timeslots is? If so, what is it and how do you know? If not, what are the possibilities?

Checkpoint

The procedure used in Example 22 to color the graph is not guaranteed to result in a graph that has the minimum number of colors possible, but it is usually results in a coloring that is close to the chromatic number.

Your Turn 12.22

The given figure shows the same graph colored in several ways. The largest clique of the graph has three vertices. Use this information to answer each question.
Three graphs. Graph 1 has 2 vertices in red, 2 vertices in blue, 1 vertex in purple, and 2 vertices in green. Edges from the first red vertex lead to two blue vertices, one green vertex, and one purple vertex. An edge from the second blue vertex leads to the purple vertex. Edges from the purple vertex lead to the second red and second green vertices. Graph 2 has 1 vertex in red, 3 vertices in blue, 2 vertices in green, and 1 vertex in purple. Edges from the red vertex lead to the green vertices, one blue vertex, and one purple vertex. The two green vertices are connected by an edge. The first blue connects with the purple via an edge. The purple connects with the other two blue vertices via edges. The second and third blue vertices are connected by an edge. Graph 3 has 1 red vertex, 2 orange vertexes, 1 green vertex, 2 blue vertices, and 1 purple vertex. Edges from the red vertex lead to orange, green, purple, and blue vertices. The first orange vertex connects with the green. The first blue connects with the first purple. This purple connects with the second orange and second blue vertices via edges. The second orange and the second blue are connected via an edge.
Figure 12.108 Possible Colorings of the Same Graph
1.
Is the graph planar? What does your answer tell you about the chromatic number?
2.
What is the lowest possible chromatic number of this graph based on the size of any cliques?
3.
What are the possible chromatic numbers?
4.
Which graph or graphs meet the definition of a valid graph coloring?
5.
Draw an n-coloring for the graph where n is the answer to Exercise 1.

The Four Color Problem

Two figures. The first figure shows a rectangle divided into several small blocks. The second figure is the same as that of the first figure with the addition that the blocks are shaded in 4 different colors.
Figure 12.109 Using only four colors, no two adjacent regions have the same color.

The idea of coloring graphs to solve problems was inspired by one of the most famous problems in mathematics, the “four color problem.” The idea was that, no matter how complicated a map might be, only four colors were needed to color the map so that no two regions that shared a boundary would be the same color. For many years, everyone suspected this to be true, because no one could create a map that needed more than four colors, but they couldn’t prove it was true in general. Finally, graphs were used to solve the problem!

We saw how maps can be represented as graphs in Graph Basics. Figure 12.110 from Example 12.4 shows a map of the midwestern region of the United States.

A partial map of the USA with midwestern states. The Midwestern states are North Dakota, South Dakota, Nebraska, Kansas, Minnesota, Iowa, Missouri, Wisconsin, Illinois, Indiana, Michigan, and Ohio.
Figure 12.110 Map of Midwestern States

Figure 12.111 shows how this map can be associated with a graph in which each vertex represents a state and each edge indicates the states that share a common boundary. Figure 12.112 shows the final graph.

A partial map of the USA with midwestern states. The Midwestern states are North Dakota (N D), South Dakota (S D), Nebraska (N E), Kansas (K S), Minnesota (M N), Iowa (I A), Missouri (M O), Wisconsin (W I), Illinois (I L), Indiana (I N), Michigan (M I), and Ohio (O H). Edges from N D connect with S D and M N. Edges from S D connect with N E, I A, and M N. Edges from M N connect with I A and W I. Edges from N E connect with K S, M O, and I A. Edges from I A connect with M O and I L. Edges from W I connect with I A and I L. An edge from K S connects with M O. An edge from M O connects with I L. An edge from I L connects with I N. Edges from I N connect with M I and O H. An edge from M I connects with O H.
Figure 12.111 Edge Assigned to Each Pair of Midwestern States with Common Border
A graph represents common boundaries between midwestern states. The vertices are North Dakota (N D), South Dakota (S D), Nebraska (N E), Kansas (K S), Minnesota (M N), Iowa (I A), Missouri (M O), Wisconsin (W I), Illinois (I L), Indiana (I N), Michigan (M I), and Ohio (O H). Edges from M N connect with I A and W I. Edges from N E connect with K S, M O, and I A. Edges from I A connect with M O and I L. Edges from W I connect with I A and I L. An edge from K S connects with M O. An edge from M O connects with I L. An edge from I L connects with I N. Edges from I N connect with M I and O H. An edge from M I connects with O H.
Figure 12.112 Final Graph Representing Common Boundaries between Midwestern States

Notice that the graph representing the common boundaries between midwestern states is planar, meaning that it can be drawn on a flat surface without edges crossing. As we have seen, any planar graph has a chromatic number of four or less. This very well-known fact is called the Four-Color Theorem, or Four-Color Map Theorem.

People in Mathematics

Four-Color Theorem

In the 19th century, Francis Guthrie was coloring a map of British counties and noticed that he could color so that no two adjacent counties were the same color using only four colors. This seemed to be the case for other maps as well, but he could not figure out why. He shared this with his brother, Frederick, who subsequently took the problem to his professor, August De Morgan, one of the most famous mathematicians of all time. De Morgan never was able to solve the problem, but he shared it with his colleagues. The problem continued to intrigue and perplex mathematicians for over a hundred years, inspiring discoveries in several areas of mathematics. It was finally proven by Kenneth Appel and Wolfgang Haken from the University of Illinois in 1976 using a combination of computer-aided calculations and graph theory. This was the first time in history that a mathematical theorem was proven using a computer! (Jesus Najera, “The Four-Color Theorem,” Cantor’s Paradise, a Medium publication, October 22, 2019)

Example 12.23

Using Four Colors or Fewer to Color a Graph

Find a coloring of the graph in Figure 12.110, which uses four colors or fewer. Use the resulting coloring as a guide to recolor the map in Figure 12.112. How many colors did you use? Does this support the conclusion of the Four-Color Theorem? If so, how?

Your Turn 12.23

1.
The first figure shows a map of the Island of Oahu in the State of Hawaii divided into regions, and the second figure shows a graph of the map. What is the chromatic number? Find a graph coloring that reflects the chromatic number of the graph.
A map shows the regions of Oahu. The regions are North Shore, Leeward Coast, Central, Windward Coast, and South.
Figure 12.114 Map of Oahu
A graph represents common boundaries between regions of Oahu. The five vertices are L, N, W, C, and S. Edges from L connect with N and C. Edges from N connect with W and C. Edges from W connect with C and S. An edge from S connects with S.
Figure 12.115 Graph Representing Common Boundaries between Regions of Oahu

Who Knew?

Coloring A Möbius Strip

Have you ever heard of a möbius strip? It is a flat object with only one side. This might sound theoretical, but you can make one for yourself. Take a narrow strip of paper, make a half twist in it, and tape the ends together. To prove to yourself that it has only one side, pick a point anywhere on the paper and start drawing a line. You can draw the line continuously without lifting your pen from the paper and eventually, you will get back to the point at which you started. Since you never had to flip over the paper, you have just proved it has one side!

Now, you might be wondering what this has to do with Graph Theory. It turns out that a map drawn on a möbius strip cannot necessarily be drawn using four colors. This doesn’t contradict the Four-Color Theorem, which only applies to graphs that are planar. A möbius strip does not live on a “plane,” or flat surface, which means the maps are not always planar like those drawn on a flat piece of paper. In the case of a möbius strip, it is the Six-Color Map Theorem! Figure 12.116 is an example of a möbius strip with a map that requires five colors.

A Mobius strip is shaded in five different colors.
Figure 12.116 A Five-Coloring on a Möbius Strip

Check Your Understanding

For the following exercises, determine whether each statement is always true or sometimes true.
25.
A trail is a path.
26.
A trail is a walk.
27.
A walk is a path.
28.
A circuit is a trail.
29.
A directed cycle is a path.
30.
A circuit is a directed cycle.
31.
A directed cycle is a circuit.
32.
If a graph has an n-coloring, then its chromatic number is n.
33.
If the chromatic number of a graph is n, then it has an n-coloring.
34.
If a graph is planar, then it has a chromatic number of at most four.
For the following exercise, fill in the blanks to make the statement true.
35.
A walk that ____________ is a trail.
36.
A trail that ____________ is a circuit.
37.
A circuit that ___________ is a directed cycle.
38.
A closed walk that ____________ is a circuit.
39.
A complete graph with n vertices has a chromatic number of_____.
40.
A graph with a clique with n-vertices has a chromatic number of _________ n.

Section 12.4 Exercises

For the following exercises, identify each sequence of vertices from the figure as a walk, trail, and/or path. Select all that apply.
A graph shows 16 vertices arranged n 4 rows and 4 columns. The vertices are as follows. Row 1: A, B, C, D. Row 2: E, F, G, H. Row 3: I, J, K, L. Row 4: M, N, O, P. The vertices are connected to the adjacent vertices via edges.
1.
ABFGKJFB
2.
GKONJKL
3.
FJKGBA
4.
IJKLKJN
5.
MNOKLH
6.
AFKP
7.
NJFBCGFE
8.
EFJIE
For the following exercises, identify each sequence of vertices from Figure 12.134 as a closed walk, circuit (closed trail), and/or directed cycle (closed path). Select all that apply.
9.
ABFGKJFBA
10.
GKONJKL
11.
FJNOKJIEF
12.
IJKGFEI
13.
MNOKJIM
14.
NJFBCGFJN
15.
ABGFEA
16.
EFGKJFBAE
For the following exercises, use the graphs shown. Identify the graph or graphs with the given characteristics. Four graphs. Graph 1: two red vertices, two blue vertices, and two purple vertices are present. All the vertices are interconnected. Graph 2: vertices are arranged in three columns. Column 1: P, R, B. Column 2: B. Column 3: P, R, P. In the first column, an edge connects P to R and another edge connects R to B. In the third column, an edge connects P to R and another edge connects R to P. In the second column, edges from B connect to the two R vertices. An edge from B in the first column connects with R in the third column. Graph 3 shows alternating 4 B and 4 R vertices in a circle. Graph 4: nine vertices are arranged in 3 rows and 3 columns. Row 1: B, G, B. Row 2: P, R, P. Row 3: B, G, B. The outer vertices are connected with edges to form a square. Horizontal, vertical, and diagonal edges connect the center vertext to the outer vertices.
17.
The colors do not follow the definition of a graph coloring.
18.
The graph is a two-coloring.
19.
The graph is a three-coloring.
20.
The graph is a four-coloring.
21.
The graph is planar.
22.
The graph has a chromatic number of two.
23.
Fewer colors could be used to color the graph.
24.
The chromatic number is more than four.
25.
The Four-Color Theorem applies to the graph.
For the following exercises, complete the sequence of vertices from the graph to create the indicated kind of closed walk.
A graph with 8 vertices. The vertices are a, b, c, d, e, f, g, and h. Edges connect a b, b c, a e, b d, c h, c d, d e, e f, d f, f g, g h, and h f.
26.
Closed path: ab → □ → □ → □ → a
27.
Closed path that visits edge ed twice: ed → □ → □ → □ → e
28.
Directed cycle: ea → □ → □ → □ → e
29.
Directed cycle: bd → □ → □ → □ → b
30.
Circuit that visits vertex d twice: bcd → □ → □ → □ → b
31.
Circuit that visits vertex f twice: ghf → □ → □ → □ → g
For the following exercises, use the graphs shown.
Four graphs. Graph 1 has six vertices: a, b, c, d, e, and f. The edges connect a b, b c, b e, d e, and e f. Graph 2 has seven vertices: p, s, u, q, r, t, and v. The edges connect p s, s u, s q, p q, q r, q t, r t, and t v. Graph 3 has 8 vertices: g, h, i, j, k, o, m, and n. All vertices are interconnected. Graph 4 has 9 vertices: a, b, c, d, e, f, g, h, and i. The edges connect a b, b c, a d, c f, f e, e i, e h, h g, and g d.
32.
Find the chromatic number n for graph 1 and give an n-coloring.
33.
Find the chromatic number n for graph 2 and give an n-coloring.
34.
Find the chromatic number n for graph 3 and give an n-coloring.
35.
Find the chromatic number n for graph 4 and give an n-coloring.
For the following exercises, indicate the smallest and largest possible chromatic number of the graph described.
36.
The graph has 15 vertices and contains a clique with 9 vertices.
37.
A planar graph with 100 vertices and a clique with 3 vertices.
38.
A planar graph with more than 2 vertices and no cliques.
39.
A complete graph with 2,123 vertices.
40.
In chess, a knight can move in any direction, but it must move two spaces then turn and move one more space. The 8 possible moves a knight can make from a space in the center of a five-by-five grid are shown in the first figure. A knight’s tour is a sequence of moves by a knight on a chessboard (of any size) such that the knight visits every square exactly once. If the knight’s tour brings the knight back to its starting position on the board, it is called a closed knight’s tour. Otherwise, it is called an open knight’s tour. Determine if the closed knight’s tour in the second figure is most accurately described as a closed walk, a circuit, or a directed cycle. Explain your reasoning.
An illustration shows a 5 by 5 square chess board. A knight is at the center of the board. The knight moves in an L-shape and it is indicated by 8 arrows. It moves either two steps left or right followed by one step up or down, or two steps up or down followed by one step left or right.
A graph represents a knight's moves on a 5 by 6 chessboard. The knight is at the bottom-left square. The knight moves in an L-shape. The movement of the knight inside the 5 by 6 board is mapped and connected via edges.
41.
An open knight’s tour on a five-by-five board is shown in the figure. Is it most accurately described as a walk, a trail, or a path?
A graph represents a knight's moves on a 5 by 5 chessboard. The knight is at the center square of the board. The knight moves in an L-shape. The movement of the knight inside the 5 by 5 board is mapped and connected via edges.
42.
A knight’s tour is not possible on a four-by-four board like the one shown in the figure. Find an open tour of the board in which the knight is permitted to travel through a given space more than once to achieve the goal of visiting every space. Is your tour most accurately described as a walk, trail, or path? Explain why.
A 4 by 4 square chess board. A knight is at the bottom-left of the board.
The neighborhood of Pines West has three cul-de-sacs that meet at an intersection as shown in the figure. A postal delivery person starts at the intersection and visits each house in a cul-de-sac once, returns to the intersection, visits each house in the next cul-de-sac, and so on, returning to the intersection when finished.
43.
Describe how the route can be represented as a graph. If there is no backtracking, in other words, the person never reverses direction, is the route followed by the postal delivery person best described as a walk, trail, path, closed walk, circuit, or directed cycle? Explain your reasoning.
A map of Pines West. The map shows a start point at the center leading to three paths. Each path has six vertices. The start point is indicated by a vertex.
44.
Draw the graph for the route described in the neighborhood. Find its chromatic number. Find a map coloring that shows the chromatic number.
45.
When radio towers are within range of each other, they must use different frequencies. In the graph, the vertices represent the towsers, and the edges indicate the towers are in range of each other. Use graph colorings to determine the number of frequencies needed to avoid two towers in the same range being assigned the same frequency. Give an example of a coloring to support your conclusion.
A graph shows a quadrilateral and a triangle. One of the vertices of the quadrilateral is connected with one of the vertices of the triangle. The quadrilateral has two diagonal edges.
46.
A Sudoku puzzle consists of a nine-by-nine grid which is subdivided into nine three-by-three smaller grids. Given an incomplete grid, the goal is to complete it in such a way that each row contains the numbers 1 through 9, each column contains the numbers 1 through 9, and each three by three grid contains the numbers 1 through 9 as shown in the figure. If a graph were drawn with a vertex to represent each entry in the grid, what should the edges represent so that a nine-coloring of the graph would be a solution to the puzzle?
Two Sudoku puzzle. First Sudoku puzzle has 9 rows and 9 columns. Row 1: 8, empty, empty, 9, 3, empty, empty, empty, and 2. Row 2: empty, empty, 9, empty, empty, empty, empty, 4, and empty. Row 3: 7, empty, 2, 1, empty, empty, 9, 6, and empty. Row 4: 2, empty, empty, empty, empty, empty, empty, 9, and empty.  Row 5: empty, 6, empty, empty, empty, empty, empty, 7, and empty. Row 6: empty, 7, empty, empty, empty, 6, empty, empty, and 5. Row 7: empty, 2, 7, empty, empty, 8, 4, empty, and 6. Row 8: empty, 3, empty, empty, empty, empty, 5, empty, and empty. Row 9: 5, empty, empty, empty, 6, 2, empty, empty, and 8. Second Sudoku puzzle has 9 rows and 9 columns. Row 1: 8, 4, 6, 9, 3, 7, 1, 5, and 2. Row 2: 3, 1, 9, 6, 2, 5, 8, 4, and 7. Row 3: 7, 5, 2, 1, 8, 4, 9, 6, and 3. Row 4: 2, 8, 5, 7, 1, 3, 6, 9, and 4. Row 5: 4, 6, 3, 8, 5, 9, 2, 7, and 1. Row 6: 9, 7, 1, 2, 4, 6, 3, 8, and 5. Row 7: 1, 2, 7, 5, 9, 8, 4, 3, and 6. Row 8: 6, 3, 8, 4, 7, 1, 5, 2, and 9. Row 9: 5, 9, 4, 3, 6, 2, 7, 1, and 8.
At a wedding reception, the bride and groom would like their family and friends to get to know each other better. They have decided that if two people know each other, they will not seat them at the same table. The following is a list of guests and who they know. Guests A, B, C, and D all know each other; guests E, F, G, and H all know each other; guests I, J, and K all know each other; guests P, Q and R all know each other, guests L, M, and O all know each other. Additionally, I knows D and I knows G, J knows M, K knows P, N knows L, and N knows O.
47.
Draw a graph to show the relationships.
48.
Determine the minimum number of tables needed to seat the guests so that they will sit with people they don’t know.
49.
Give a coloring to support your conclusion.
The map of the states of Imaginaria is given. Use the figure to answer the following exercises.
A map of Imaginaria. It has four regions: Fictionville, Illusionham, Mythbury, and Pretendstead.
50.
Draw a graph to represent the map.
51.
Determine the chromatic number of the graph you found.
52.
Give a graph coloring that supports your answer in the previous question.
53.
Color the provided map to correspond with the coloring you found in the previous question.
Citation/Attribution

Want to cite, share, or modify this book? This book uses the Creative Commons Attribution License and you must attribute OpenStax.

Attribution information
  • If you are redistributing all or part of this book in a print format, then you must include on every physical page the following attribution:
    Access for free at https://openstax.org/books/contemporary-mathematics/pages/1-introduction
  • If you are redistributing all or part of this book in a digital format, then you must include on every digital page view the following attribution:
    Access for free at https://openstax.org/books/contemporary-mathematics/pages/1-introduction
Citation information

© Apr 17, 2023 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution License . The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.