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

12.5 Euler Circuits

Contemporary Mathematics12.5 Euler Circuits

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
A delivery vehicle.
Figure 12.117 Delivery trucks move goods from place to place. (credit: “Mack Midliner” by Jason Lawrence/Flickr, CC BY 2.0)

Learning Objectives

After completing this section, you should be able to:

  1. Determine if a graph is connected.
  2. State the Chinese postman problem.
  3. Describe and identify Euler Circuits.
  4. Apply the Euler Circuits Theorem.
  5. Evaluate Euler Circuits in real-world applications.

The delivery of goods is a huge part of our daily lives. From the factory to the distribution center, to the local vendor, or to your front door, nearly every product that you buy has been shipped multiple times to get to you. If the cost and time of that delivery is too great, you will not be able to afford the product. Delivery personnel have to leave from one location, deliver the goods to various places, and then return to their original location and do all of this in an organized way without losing money. How do delivery services find the most efficient delivery route? The answer lies in graph theory.

Connectedness

Before we can talk about finding the best delivery route, we have to make sure there is a route at all. For example, suppose that you were tasked with visiting every airport on the graph in Figure 12.118 by plane. Could you accomplish that task, only taking direct flight paths between airports listed on this graph? In other words, are all the airports connected by paths? Or are some of the airports disconnected from the others?

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.118 Major Central and South Florida Airports

In Figure 12.118, we can see TPA is adjacent to PBI, FLL, MIA, and EYW. Also, there is a path between TPA and MCO through FLL. This indicates there is a path between each pair of vertices. So, it is possible to travel to each of these airports only taking direct flight paths and visiting no other airports. In other words, the graph is connected because there is a path joining every pair of vertices on the graph. Notice that if one vertex is connected to each of the others in a graph, then all the vertices are connected to each other. So, one way to determine if a graph is connected is to focus on a single vertex and determine if there is a path between that vertex and each of the others. If so, the graph is connected. If not, the graph is disconnected, which means at least one pair of vertices in a graph is not joined by a path. Let’s take a closer look at graph X in Figure 12.119. Focus on vertex a. There is a path between vertices a and b, but there is no path between vertex a and vertex c. So, Graph X is disconnected.

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. Graph Y is the same as that of graph X. The point where they overlap has a vertex, g.
Figure 12.119 Connected vs. Disconnected

When you are working with a planar graph, you can also determine if a graph is connected by untangling it. If you draw it so that so that none of the edges are overlapping, like we did with Graph X in Figure 12.119, it is easier to see that the graph is disconnected.

Three graphs. Graph X, version 1 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. Graph X, version 2 has 2 triangles. 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. Graph X, version 3 has two concentric triangles. Inner triangle: the vertices a, b, and e are connected by three edges. Outer triangle: the vertices, c, d, and f are connected by three edges.
Figure 12.120 Untangling Graph X

Versions 2 and 3 of Graph X in Figure 12.120 each have the same number of vertices, number of edges, degrees of the vertices, and pairs of adjacent vertices as version 1. In other words, each version retains the same structure as the original graph. Since versions 2 and 3 of Graph X, do not have overlapping edges, it is easier to identify pairs of vertices that do not have paths between them, and it is more obvious that Graph X is disconnected. In fact, there are two completely separate, disconnected subgraphs, one with the vertices in {a, b, e}, and the other with the vertices {c, d, f}

These sets of vertices together with all of their edges are called components of Graph X. A component of a graph is a subgraph in which there is a path between each pair of vertices in the subgraph, but no edges between any of the vertices in the subgraph and a vertex that is not in the subgraph.

Now let’s focus on Graph Y from Figure 12.119. As in Graph X, there is a path between vertices a and b, as well as between vertices a and e, but Graph Y is different from Graph X because of vertex g. Not only is there a path between vertices a and g, but vertex g bridges the gap between a and c with the path a → b → g → c. Similarly, there is a path between vertices a and d and vertices a and f: a → b → g → d, a → b → g → d → f. Since there is a path between vertex a and every other vertex, Graph Y is connected. You can also see this a bit more clearly by untangling Graph Y as in Figure 12.121. Even when Y is drawn so that the edges do not overlap, the graph cannot be drawn as two separate, unconnected pieces. In other words, Graph Y has only one component with the vertices {a, b, c, d, e, f}.

We can give an alternate definition of connected and disconnected using the idea of components. A graph is connected if it has only one component. A graph is disconnected if it has more than one component. These alternate definitions are equivalent to the previous definitions. This means that you can confirm a graph is connected or disconnected either by checking to see if there is a path between each vertex and each other vertex, or by identifying the number of components. A graph is connected if it has only one component.

Three graphs. Graph Y, version 1 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. Graph Y, version 2 has a triangle and a kite. The vertices a, b, and e are connected by three edges and it resembles a triangle. The vertices, g, c, d, and f are connected by four edges and it resembles a kite. The point, g lies on the edge, e b. Graph Y, version 3 has a kite inside a triangle. The vertices c, d, and f are connected by three edges and it resembles a triangle. The vertices, g, b, e, and a are connected by four edges and it resembles a kite. The point, g lies on the edge, c d.
Figure 12.121 Untangling Graph Y

Example 12.24

Determining If a Graph Is Connected or Disconnected

Use Figure 12.122 to answer each question.

Graph E has four vertices: a, b, c, and d. Edges connect d c, d a, and d b.
Figure 12.122 Graph E
  1. Find a path between vertex a and every other vertex on the graph, if possible.
  2. Identify all the components of Graph E.
  3. Determine whether the graph is connected or disconnected and explain how you know.

Your Turn 12.24

1.
Determine whether each graph is connected or disconnected and identify the set of vertices that make up each of its components.
Six graphs. Each graph has four vertices: a, b, c, and d. Graph F: edges connect d c and d a. Graph G: edges connect a b, a d, and d c. Graph H: edges connect d c, d a, and c b. Graph I: edges connect d c, c b, d a, and a b. Graph J: edges connect a d and c b. Graph K: an edge connects b and d.
Figure 12.123

Example 12.25

Applying Connectedness

The U.S. Interstate Highway System extends throughout the 48 contiguous states. It also has routes in the states of Hawaii and Alaska, and the commonwealth of Puerto Rico. Consider a graph representing the U.S. Interstate Highway System, in which there is a vertex for each of the 50 states and Puerto Rico, and an edge is drawn between any two vertices representing states that are connected by a highway in that system. Would this graph be connected or disconnected? Explain your reasoning.

Your Turn 12.25

1.
“Six degrees of separation” is the idea that any two people on Earth are connected by at most six social connections. Assume that this is true. Consider a graph in which each vertex is a person on Earth, and each edge is a social connection. Would this graph be connected or disconnected? Explain your reasoning.

Origin of Euler Circuits

The city of Konigsberg, modern day Kaliningrad, Russia, has waterways that divide up the city. In the 1700s, the city had seven bridges over the various waterways. The map of those bridges is shown in Figure 12.124. The question as to whether it was possible to find a route that crossed each bridge exactly once and return to the starting point was known as the Konigsberg Bridge Problem. In 1735, one of the most influential mathematicians of all time, Leonard Euler, solved the problem using an area of mathematics that he created himself, graph theory!

A map shows the bridges of Konigsberg in the 1700s.
Figure 12.124 Map of the Bridges of Konigsberg in 1700s (credit: “Konigsberg Bridge” by Merian Erben/Wikimedia Commons, Public Domain)

Euler drew a multigraph in which each vertex represented a land mass, and each edge represented a bridge connecting them, as shown in Figure 12.125. Remember from Navigating Graphs that a circuit is a trail, so it never repeats an edge, and it is closed, so it begins and ends at the same vertex. Euler pointed out that the Konigsberg Bridge Problem was the same as asking this graph theory question: Is it possible to find a circuit that crosses every edge? Since then, circuits (or closed trails) that visit every edge in a graph exactly once have come to be known as Euler circuits in honor of Leonard Euler.

Euler was able to prove that, in order to have an Euler circuit, the degrees of all the vertices of a graph have to be even. He also proved that any graph with that characteristic must have an Euler circuit. So, saying that a connected graph is Eulerian is the same as saying it has vertices with all even degrees, known as the Eulerian circuit theorem.

A graph of Konigsberg Bridges has four vertices. The vertices are connected with edges forming two right cones.
Figure 12.125 Graph of Konigsberg Bridges

To understand why the Euler circuit theorem is true, think about a vertex of degree 3 on any graph, as shown in Figure 12.126.

Two illustrations. The first illustration shows a vertex, 3. Two arrows point to it and an arrow points away from it. The second illustration shows a vertex, 3. Two arrows point away from it and an arrow points to it.
Figure 12.126 A Vertex of Degree 3

First imagine the vertex of degree 3 shown in Figure 12.126 is not the starting vertex. At some point, each edge must be traveled. The first time one of the three edges is traveled, the direction will be toward the vertex, and the second time it will be away from the vertex. Then, at some point, the third edge must be traveled coming in toward the vertex again. This is a problem, because the only way to get back to the starting vertex is to then visit one of the three edges a second time. So, this vertex cannot be part of an Euler circuit.

Next imagine the vertex of degree 3 shown in Figure 12.126 is the starting vertex. The first time one of the edges is traveled, the direction is away from the vertex. At some point, the second edge will be traveled coming in toward the vertex, and the third edge will be the way back out, but the starting vertex is also the ending vertex in a circuit. The only way to return to the vertex is now to travel one of the edges a second time. So, again, this vertex cannot be part of an Euler circuit.

For the same reason that a vertex of degree 3 can never be part of an Euler circuit, a vertex of any odd degree cannot either. We can use this fact and the graph in Figure 12.127 to solve the Konigsberg Bridge Problem. Since the degrees of the vertices of the graph in Figure 12.126 are not even, the graph is not Eulerian and it cannot have an Euler circuit. This means it is not possible to travel through the city of Konigsberg, crossing every bridge exactly once, and returning to your starting position.

A graph of Konigsberg Bridges has four vertices. The vertices are connected with edges forming two right cones. The degrees of the vertices are 3, 3, 5, and 3.
Figure 12.127 Degrees of Vertices in Konigsberg Bridge Multigraph

Chinese Postman Problem

At Camp Woebegone, campers travel the waterways in canoes. As part of the Camp Woebegone Olympics, you will hold a canoeing race. You have placed a checkpoint on each of the 11 different streams. The competition requires each team to travel each stream, pass through the checkpoints in any order, and return to the starting line, as shown in the Figure 12.128.

A map of canoe event checkpoints. The map has vertices labeled from A to K. The start point is also marked on the map.
Figure 12.128 Map of Canoe Event Checkpoints

Since the teams want to go as fast as possible, they would like to find the shortest route through the course that visits each checkpoint and returns to the starting line. If possible, they would also like to avoid backtracking. Let’s visualize the course as a multigraph in which the vertices represent turns and the edges represent checkpoints as in Figure 12.129.

A multigraph of canoe event checkpoints. The map has seven vertices. The vertices are connected via edges resembling a closed trail. The start point is also marked on the map.
Figure 12.129 Multigraph of Canoe Event

The teams would like to find a closed walk that repeats as few edges as possible while still visiting every edge. If they never repeat an edge, then they have found a closed trail, which is a circuit. That circuit must cover all edges; so, it would be an Euler circuit. The task of finding a shortest circuit that visits every edge of a connected graph is often referred to as the Chinese postman problem. The name Chinese postman problem was coined in honor of the Chinese mathematician named Kwan Mei-Ko in 1960 who first studied the problem.

If a graph has an Euler circuit, that will always be the best solution to a Chinese postman problem. Let’s determine if the multigraph of the course has an Euler circuit by looking at the degrees of the vertices in Figure 12.130. Since the degrees of the vertices are all even, and the graph is connected, the graph is Eulerian. It is possible for a team to complete the canoe course in such a way that they pass through each checkpoint exactly once and return to the starting line.

A graph with seven vertices. The degrees of the vertices are 4, 4, 4, 4, 2, 2, and 2.
Figure 12.130 Degrees of Vertices in Graph of Canoe Event

Example 12.26

Understanding Eulerian Graphs

A postal delivery person must deliver mail to every block on every street in a local subdivision. Figure 12.131 is a map of the subdivision. Use the map to answer each question.

A map of a subdivision. The map has nine sections. Each section has four blocks. The entrance to the subdivision is at the bottom.
Figure 12.131 Map of Subdivision
  1. Draw a graph or multigraph to represent the subdivision in which the vertices represent the intersections, and the edges represent streets.
  2. Is your graph connected? Explain how you know.
  3. Determine the degrees of the vertices in the graph.
  4. Is your graph an Eulerian graph?
  5. Is it possible for the postal delivery person to visit each block on each street exactly once? Justify your answer.

Your Turn 12.26

A pest control service has at least one customer on every block of every street or cul-de-sac in a neighborhood. Use the map of the neighborhood to answer each question.
A map of a neighborhood. The map has nine sections. Each section has four blocks. A semicircular section is on each side. It has one block, each. The entrance is at the bottom-right.
Figure 12.133 Map of Neighborhood
1.
Draw a graph or multigraph of the neighborhood in which the vertices represent intersections, and the edges represent the streets between them.
2.
Is your graph connected? Explain how you know.
3.
Determine the degrees of the vertices in the graph.
4.
Is your graph an Eulerian graph?
5.
Is it possible for the postal delivery person to visit each block on each street exactly once and start and end at the same position? Justify your answer.

Identifying Euler Circuits

Solving the Chinese postman problem requires finding a shortest circuit through any graph or multigraph that visits every edge. In the case of Eulerian graphs, this means finding an Euler circuit. The method we will use is to find any circuit in the graph, then find a second circuit starting at a vertex from the first circuit that uses only edges that were not in the first circuit, then find a third circuit starting at a vertex from either of the first two circuits that uses only edges that were not in the first two circuits, and then continue this process until all edges have been used. In the end, you will be able to link all the circuits together into one large Euler circuit.

Let’s find an Euler circuit in the map of the Camp Woebegone canoe race. In Figure 12.134, we have labeled the edges of the multigraph so that the circuits can be named. In a multigraph it is necessary to name circuits using edges and vertices because there can be more than one edge between adjacent vertices.

A multigraph of canoe race. The multigraph has 7 vertices. The vertices are numbered 1 to 7. The vertex is labeled start. Edges are as follows. A: 1 to 2. B: 2 to 3. C: 3 to 4. D: 2 to 6. E: 6 to 7. F: 7 to 2. G: 4 to 5. H: 5 to 3. I: 5 to 1. J, curved edge: 5 to 1. K: 1 to 3.
Figure 12.134 Multigraph of Canoe Race with Vertices and Edges Labeled

We will begin with vertex 1 because it represents the starting line in this application. In general, you can start at any vertex you want. Find any circuit beginning and ending with vertex 1. Remember, a circuit is a trail, so it doesn’t pass through any edge more than once. Figure 12.135 shows one possible circuit that we could use as the first circuit, 1 → A → 2 → B → 3 → C → 4 → G → 5 → J → 1.

A multigraph of canoe race. The multigraph has 7 vertices. The vertices are numbered 1 to 7. The vertex is labeled start. Edges are as follows. A: 1 to 2. B: 2 to 3. C: 3 to 4. D: 2 to 6. E: 6 to 7. F: 7 to 2. G: 4 to 5. H: 5 to 3. I: 5 to 1. J, curved edge: 5 to 1. K: 1 to 3. The edges, A, B, C, J, and G are in blue.
Figure 12.135 First Circuit

From the edges that remain, we can form two more circuits that each start at one of the vertices along the first circuit. Starting at vertex 3 we can use 3 → H → 5 → I → 1 → K → 3 and starting at vertex 2 we can use 2 → D → 6 → E → 7 → F → 2, as shown in Figure 12.136.

A multigraph of canoe race. The multigraph has 7 vertices. The vertices are numbered 1 to 7. The vertex is labeled start. Edges are as follows. A: 1 to 2. B: 2 to 3. C: 3 to 4. D: 2 to 6. E: 6 to 7. F: 7 to 2. G: 4 to 5. H: 5 to 3. I: 5 to 1. J, curved edge: 5 to 1. K: 1 to 3. The edges, A, B, C, J, and G are in blue. The edges, I, K, and H are in green. The edges, F, D, and E are in red.
Figure 12.136 Second and Third Circuits

Now that each of the edges is included in one and only once circuit, we can create one large circuit by inserting the second and third circuits into the first. We will insert them at their starting vertices 2 and 3

1A2B3C4G5J11A2B3C4G5J1

becomes

1A2D6E7F2B3H5I1K3C4G5J11A2D6E7F2B3H5I1K3C4G5J1

Finally, we can name the circuit using vertices, 1 → 2 → 6 → 7 → 2 → 3 → 5 → 1 → 3 → 4 → 5 → 1, or edges, ADEFBHIKC → G → J.

Let's review the steps we used to find this Eulerian Circuit.

Steps to Find an Euler Circuit in an Eulerian Graph

Step 1 - Find a circuit beginning and ending at any point on the graph. If the circuit crosses every edges of the graph, the circuit you found is an Euler circuit. If not, move on to step 2.

Step 2 - Beginning at a vertex on a circuit you already found, find a circuit that only includes edges that have not previously been crossed. If every edge has been crossed by one of the circuits you have found, move on to Step 3. Otherwise, repeat Step 2.

Step 3 - Now that you have found circuits that cover all of the edges in the graph, combine them into an Euler circuit. You can do this by inserting any of the circuits into another circuit with a common vertex repeatedly until there is one long circuit.

Example 12.27

Finding an Euler Circuit

Use Figure 12.137 to answer each question.

Graph F has five vertices. The vertices are a, b, c, d, and e. The edges connect a c, a b, e c, e b, c b, c d, and b d.
Figure 12.137 Graph F
  1. Verify the Graph F is Eulerian.
  2. Find an Euler circuit that begins and ends at vertex c.

Your Turn 12.27

Use Graphs X and Y to answer each question.
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. Graph Y is the same as that of graph X. The point where they overlap has a vertex, g.
Figure 12.141
1.
Which graph does not have an Euler circuit? Explain how you know.
2.
Find an Euler circuit in the other graph.

Eulerization

The Chinese postman problem doesn’t only apply to Eulerian graphs. Recall the postal delivery person who needed to deliver mail to every block of every street in a subdivision. We used the map in Figure 12.142 to create the graph in Figure 12.143.

A map of a subdivision. The map has nine sections. Each section has four blocks. The entrance to the subdivision is at the bottom.
Figure 12.142 Map of Subdivision
A graph of subdivision has 16 vertices arranged in 4 rows and 4 columns. The vertices are connected to form 9 squares.
Figure 12.143 Graph of Subdivision

Since the graph of the subdivision has vertices of odd degree, there is no Euler circuit. This means that there is no route through the subdivision that visits every block of every street without repeating a block. What should our delivery person do? They need to repeat as few blocks as possible. The technique we will use to find a closed walk that repeats as few edges as possible is called eulerization. This method adds duplicate edges to a graph to create vertices of even degree so that the graph will have an Euler circuit.

In Figure 12.144, the eight vertices of odd degree in the graph of the subdivision are circled in green. We have added duplicate edges between the pairs of vertices, which changes the degrees of the vertices to even degrees so the resulting multigraph has an Euler circuit. In other words, we have eulerized the graph.

Two graphs. The first graph has 16 vertices arranged in 4 rows and 4 columns. The vertices are connected to form 9 squares. The second graph has 16 vertices arranged in 4 rows and 4 columns. The vertices are connected to form 9 squares. On each side, a curved edge connects the center two vertices.
Figure 12.144 An Eulerized Graph

The duplicate edges in the eulerized graph correspond to blocks that our delivery person would have to travel twice. By keeping these duplicate edges to a minimum, we ensure the shortest possible route. It can be challenging to determine the fewest duplicate edges needed to eulerize a graph, but you can never do better than half the number of odd vertices. In the graph in Figure 12.144, we have found a way to fix the eight vertices of odd degree with only four duplicate edges. Since four is half of eight, we will never do better.

Checkpoint

IMPORTANT! The duplicate edges that we add indicate places where the route will pass twice. An entirely new edge between two vertices that were not previously adjacent would indicate that our postal delivery person created a new road through someone’s property! So, we can duplicate existing edges, but we cannot create new ones.

Example 12.28

Eulerizing Graphs

Use Graph A and multigraphs B, C, D, and E given in Figure 12.145 to answer the questions.

Five graphs. Each graph has five vertices, a to e. Graph A: edge F, a to c. Edge H, a to d. Edge G, a to b. Edge I, b to c. Edge J, b to d. Edge K, c to e. Edge L, d to e. Multigraph B: edge F, a to c. Edge H, a to d. Edges G and M, a to b. Edge I, b to c. Edge J, b to d. Edge N, c to d. Edge K, c to e. Edge L, d to e. Multigraph C: edge F, a to c. Edge H, a to d. Edges M and G, a to b. Edges I and P, b to c. Edges J and Q, b to d. Edge K, c to e. Edge L, d to e. Multigraph D: edge F, a to c. Edges H and A, a to d. Edge G, a to b. Edges P and I, b to c. Edge J, b to d. Edge K, c to e. Edge L, d to e. Multigraph E: edge F, a to c. Edge H, a to d. Edge I, b to c. Edges J and a, b to d. Edges K and S, c ad e. Edge L, d to e.
Figure 12.145 Graph A and Multigraphs B through E
  1. Which of the multigraphs are not eulerizations of Graph A? Explain your answer.
  2. Which eulerization of Graph A uses the fewest duplicate edges? How many does it use?
  3. Is it possible to eulerize Graph A using fewer duplicate edges than your answer to part 2? If so, give an example. If not, explain why not.

Your Turn 12.28

1.
Create an eulerization using the fewest duplicate edges possible for Graph Z.
Graph Z has four vertices: a, b, c, and d. The edges connect a b, b d, d c, c a, and a d.
Figure 12.146 Graph Z

Checkpoint

IMPORTANT! Since only duplicate edges can be added to eulerize a graph, it is not possible to eulerize a disconnected graph.

WORK IT OUT

A map of The Magical Land of Oz. The regions are Gillikin Country, Munchkin Country, Emerald City, Winkie Country, and Quadling Country.
Figure 12.147 Map of the Magical Land of Oz (credit: “Map of Oz within the surrounding deserts” by L. Frank Baum/Wikimedia Commons, Public Domain)

In The Wonderful Wizard of Oz, written by L. Frank Baum and illustrated by W. W. Denslow, the region of the Emerald City lies at the center of the magical land of Oz, with Gillikin Country to the north, Winkie Country to the east, Munchkin Country to the west, and Quadling Country to the south. Munchkin Country and Winkie Country each shares a border with Gillikin Country and Quadling Country. Let’s apply graph theory to Dorothy’s famous journey through Oz. Draw a graph in which each vertex is one of the regions of Oz. Then answer each question:

  1. Is there an Euler trail circuit that Dorothy could follow, instead of the yellow brick road, to lead her from the land of the Munchkins, through all the regions of Oz and back, passing over each border exactly once? If not, how could the graph be Eulerized most efficiently?
  2. What is the chromatic number of the graph? Find a graph coloring that demonstrates your answer and use it to draw and color a graph of Oz.

Check Your Understanding

For the following exercises, determine whether each statement is always true, sometimes true, or never true.
41.
A disconnected graph has only one component.
42.
A graph that has all vertices of even degree is connected.
43.
There is a route through the city of Konigsberg that a person may pass over each bridge exactly once and return to the starting point.
44.
A graph with vertices of all even degree is Eulerian.
45.
An Eulerian graph has all vertices of even degree.
46.
An Euler circuit is a closed trail.
47.
An Euler circuit is a closed path
48.
To eulerize a graph, add new edges between previously nonadjacent vertices until no vertices have odd degree.
49.
To eulerize a graph, add duplicate edges between adjacent vertices until no vertices have odd degree.
50.
The number of duplicate edges required to eulerize a graph is half the number of vertices of odd degree.

Section 12.5 Exercises

Use Graphs A, B, C, D, E, F, G, H, and I to answer the following exercises. Identify any graph or graphs with the given characteristics or indicate that none do.
Nine graphs. Graph A: edges connect b c, c d, d e, e f, f g, g h, h i, i b, c i, i g, g e, and e c. Graph B: two squares, m o p k, and a n q j. Multigraph C: curved and straight edges connect s r, r t, and t s. Graph D: curved and straight edges connect u v, u w, w x, and x v. An edge connects w v. Graph E: edges connect o n, n m, m o, d e, e g, g f, f d, a b, b c, c a, h i, i k, k j, and j h. Graph F: q x, x q, r t, t v, v r, t w, w u, and u s. graph D: a c, c b, b a, b c, c d, and d b. Graph H: j e e f, h i, i o, o n, n k, k j, k g, g h, h m, and m k. Multigraph I: p r, r u, u t, and t. Triple edges connect q and s. The first curved edge touches the edges, p r, and r s. The second curved edge touches the edges, p t, and t u.
Figure 12.148
1.
Connected
2.
Disconnected
3.
Exactly two components
4.
Exactly three components
5.
Exactly four components
6.
Exactly five components
7.
At least one vertex of odd degree
8.
All vertices of even degree
9.
An Euler circuit
10.
A path between vertex j and each other vertex on the same graph
Use the graphs in the previous exercise to answer the following exercises. For each exercise, list the set of vertices for each component in the given graph.
11.
Graph B
12.
Graph E
13.
Graph F
14.
Multigraph I
Use the graphs in the initial exercise to answer the following exercises. For each exercise, a graph and a vertex on the graph are given. Find a path between the given vertex and each other vertex on the graph. If this is not possible, indicate that it is not.
15.
Graph A, vertex c.
16.
Graph B, vertex m.
17.
Graph D, vertex x.
18.
Graph F, vertex w.
19.
Graph G, vertex a.
20.
Graph H, vertex e.
Use the graphs in the initial exercise to answer the following exercises. For each exercise, a graph and a vertex on the graph are given. Find an Euler circuit beginning and ending at the given vertex if one exists. If no Euler circuits exist, explain how you know that they do not.
21.
Graph A, vertex c.
22.
Graph B, vertex k.
23.
Graph D, vertex w.
24.
Graph G, vertex b.
25.
Graph H, vertex o.
26.
Multigraph I, vertex p.
For the following exercises, use the connected graphs. In each exercise, a graph is indicated. Determine if the graph is Eulerian or not and explain how you know. If it is Eulerian, give an example of an Euler circuit. If it is not, state which edge or edges you would duplicate to eulerize the graph.
Four graphs. Graph J has 16 vertices. The edges are a b, a c, a d, b e, c d, d e, e f, c g, d h, e i, f j, g h, h i, i j, g k, h m, i n, j o, k m, m n, n o, m p, n q, o q, and p q. Graph K has 12 vertices. The edges are a b, a d, b e, c d, d e, e f, c, d h, e i, f j, g h, h i, i j, h k, i m, and k m. Multigraph L has four vertices. The straight edges are labeled as follows: n q, B; no, D; q p, F; o p, G; q c, C. The curved edges are labeled as follows: q n, A; n o, E; o p, I; p q, H. Graph M has 12 vertices. The edges are labeled a b, a c, a d, b e, b f, c d, d e, e f, c g, g d, d h, h e, e i, i f, f j, g h, h i, i j, g k, h k, i m, j m, and k m.
27.
Graph J
28.
Graph K
29.
Multigraph L
30.
Graph M
31.
The figure shows a map of zoo exhibits A through P with walkways shown in gray. Draw a graph, or multigraph, to represent the routes through the zoo in which the edges represent walkways and the vertices represent turns and intersections, which are each marked with a star. Notice that there is exactly one exhibit between each pair of adjacent vertices. Label the edges with the corresponding exhibit. Use it to determine if it is possible for a visitor to begin at the entrance, view each exhibit exactly once, and end back at the entrance. If it is possible, give an example of a circuit on the graph that would represent a route the visitor could take. If it is not possible, explain why.
A map of zoo exhibits. The vertices are labeled A to P. The entrance is at the bottom.
The figure shows the map of the exhibits at an indoor aquarium with hallways shown in gray. Turns and intersections of hallways are marked with stars.
32.
Use the Euler circuit theorem and a graph in which the edges represent hallways and the vertices represent turns and intersections to explain why a visitor to the aquarium cannot start at the entrance, visit every exhibit exactly once, and return to the entrance.
A map of aquarium exhibits. The vertices are labeled A to S. The entrance is at the bottom.
33.
Use an eulerization of the graph you found to determine the least amount of backtracking necessary to allow a visitor to begin at the entrance, see every exhibit at least once, and return to the entrance. How many hallways must be covered twice? Explain your reasoning.
The map of the states of Imaginaria is given.
34.
Use a graph to determine if it is possible to travel through Imaginaria crossing each the border between each pair of states exactly once, and returning to the state in which you started.
A map of Imaginaria. It has four regions: Fictionville, Illusionham, Mythbury, and Pretendstead.
35.
Use an eulerization of the graph you found to determine the fewest borders that must be covered twice in order to cross each border at least once and return to the state in which you started. Explain your reasoning.
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.