maths.free › Combinatorics & Graph Theory › 12. Graph Theory › Euler Trails

Euler Trails

Describe and identify Euler trails.

Learning Objectives

After completing this section, you should be able to:

  1. Describe and identify Euler trails.
  2. Solve applications using Euler trails theorem.
  3. Identify bridges in a graph.
  4. Apply Fleury’s algorithm.
  5. Evaluate Euler trails in real-world applications.

Euler Trails

If we need a trail that visits every edge in a graph, this would be called an Euler trail. Since trails are walks that do not repeat edges, an Euler trail visits every edge exactly once.

Recognizing Euler Trails

Try it.

Use to determine if each series of vertices represents a trail, an Euler trail, both, or neither. Explain your reasoning.

  1. a → b → e → g → f → c → d → e
  2. a → b → e → g → f → c → d → e → b → a → d → g
  3. g → d → a → b → e → d → c → f → g → e
Solution
  1. It is a trail only. It is a trail because it is a walk that doesn’t cover any edges twice, but it is not an Euler trail because it didn’t cover edges ad or dg.
  2. It is neither. It is not a trail because it visits ab and be twice. Since it is not a trail, it cannot be an Euler trail.
  3. It is both. It is a trail because it is a walk that doesn’t cover any edges twice, and it is an Euler trail because it visits all the edges.

The Five Rooms Puzzle

Just as Euler determined that only graphs with vertices of even degree have Euler circuits, he also realized that the only vertices of odd degree in a graph with an Euler trail are the starting and ending vertices. For example, in , Graph H has exactly two vertices of odd degree, vertex g and vertex e. Notice the Euler trail we saw in Excercise 3 of began at vertex g and ended at vertex e.

This is consistent with what we learned about vertices off odd degree when we were studying Euler circuits. We saw that a vertex of odd degree couldn't exist in an Euler circuit as depicted in . If it was a starting vertex, at some point we would leave the vertex and not be able to return without repeating an edge. If it was not a starting vertex, at some point we would return and not be able to leave without repeating an edge. Since the starting and ending vertices in an Euler trail are not the same, the start is a vertex we want to leave without returning, and the end is a vertex we want to return to and never leave. Those two vertices must have odd degree, but the others cannot.

Let’s use the Euler trail theorem to solve a puzzle so you can amaze your friends! This puzzle is called the “Five Rooms Puzzle.” Suppose that you were in a house with five rooms and the exterior. There is a doorway in every shared wall between any two rooms and between any room and the exterior as shown in . Could you find a route through the house that passes through each doorway exactly once?

Let’s represent the puzzle with a graph in which vertices are rooms (or the exterior) and an edge indicates a door between two rooms as shown in .

To pass through each doorway exactly once means that we cross every edge in the graph exactly once. Since we have not been asked to start and end at the same position, but to visit each edge exactly once, we are looking for an Euler trail. Let’s check the degrees of the vertices.

Since there are more than two vertices of odd degree as shown in , the graph of the five rooms puzzle contains no Euler path. Now you can amaze and astonish your friends!

Bridges and Local Bridges

Now that we know which graphs have Euler trails, let’s work on a method to find them. The method we will use involves identifying bridges in our graphs. A bridge is an edge which, if removed, increases the number of components in a graph. Bridges are often referred to as cut-edges. In , there are several examples of bridges. Notice that an edge that is not part of a cycle is always a bridge, and an edge that is part of a cycle is never a bridge.

Edges bf, cg, and dg are “bridges”

The graph in is connected, which means it has exactly one component. Each time we remove one of the bridges from the graph the number of components increases by one as shown in . If we remove all three, the resulting graph in has four components.

In sociology, bridges are a key part of social network analysis. Sociologists study two kinds of bridges: local bridges and regular bridges. Regular bridges are defined the same in sociology as in graph theory, but they are unusual when studying a large social network because it is very unlikely a group of individuals in a large social network has only one link to the rest of the network. On the other hand, a local bridge occurs much more frequently. A local bridge is a friendship between two individuals who have no other friends in common. If they lose touch, there is no single individual who can pass information between them. In graph theory, a local bridge is an edge between two vertices, which, when removed, increases the length of the shortest path between its vertices to more than two edges. In , a local bridge between vertices b and e has been removed. As a result, the shortest path between b and e is b → i → j → k → e, which is four edges. On the other hand, if edge ab were removed, then there are still paths between a and b that cover only two edges, like a → i → b.

The significance of a local bridge in sociology is that it is the shortest communication route between two groups of people. If the local bridge is removed, the flow of information from one group to another becomes more difficult. Let’s say that vertex b is Brielle and vertex e is Ella. Now, Brielle is less likely to hear about things like job opportunities that Ella may know about. This is likely to impact Brielle as well as the friends of Brielle.

Condensed — the full section is in OpenStax Contemporary Mathematics.

Finding an Euler Trail with Fleury’s Algorithm

Now that we are familiar with bridges, we can use a technique called Fleury’s algorithm, which is a series of steps, or algorithm, used to find an Euler trail in any graph that has exactly two vertices of odd degree.

Here are the steps involved in applying Fleury’s algorithm.

Step 1: Begin at either of the two vertices of odd degree.

Step 2: Remove an edge between the vertex and any adjacent vertex that is NOT a bridge, unless there is no other choice, making a note of the edge you removed. Repeat this step until all edges are removed.

Step 3: Write out the Euler trail using the sequence of vertices and edges that you found. For example, if you removed ab, bc, cd, de, and ef, in that order, then the Euler trail is a → b → c → d → e → f.

shows the steps to find an Euler trail in a graph using Fleury’s algorithm.

The Euler trail that was found in is t → v → w → u → t → w → y → x → v.

Finding an Euler Trail with Fleury’s Algorithm

Try it.

Use Fleury’s Algorithm to find an Euler trail for Graph J in .

Solution

Step 1: Choose one of the two vertices of odd degree, c or f, as your starting vertex. We will choose c.

Step 2: Remove edge ca, cb, or cd. None of these are cut edges so we can select any of the three. We will choose cb as shown in to be the first edge removed.

Repeat Step 2 The next choice is to remove edge ba, bd, or bf as shown in , but bf is not an option since it is a bridge. We will choose ba as shown in to be the second edge removed.

Repeat Step 2 for the third, fourth, fifth, sixth, and seventh edges. As shown in , until we get to the seventh edge there is only one option each time, ac, cd, db, and bf in that order. For the seventh edge, we must choose between fe and fg. Neither of these are bridges. We choose fe. shows that ac, cd, db, bf, and fe have been removed.

Repeat Step 2 for the eight, ninth, tenth, and eleventh edges. As shown in , there is only one option for each of these edges, eh, hi, ig, and gf, in that order.

Step 3: Write out the Euler trail using the vertices in the sequence that the edges were removed. We removed cb, ba, ac, cd, db, bf, fe, eh, hi, ig, and gf, in that order. The Euler trail is c → b → a → c → d → b → f → e → h → i → g → f.

Condensed — the full section is in OpenStax Contemporary Mathematics.

Key Concepts

  • An Euler trail exists whenever a graph has exactly two vertices of odd degree.
  • When a bridge is removed from a graph, the number of components increases.
  • A bridge is never part of a circuit.
  • When a local bridge is removed from a graph, the distance between vertices increases.
  • An edge that is part of a triangle is never a local bridge.

Practice (4)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

  1. Use to determine if each series of vertices represents a trail, an Euler trail, both, or neither. Explain your reasoning.

    1. a → b → e → g → f → c → d → e
    2. a → b → e → g → f → c → d → e → b → a → d → g
    3. g → d → a → b → e → d → c → f → g → e
    Otkrij odgovor
    1. It is a trail only. It is a trail because it is a walk that doesn’t cover any edges twice, but it is not an Euler trail because it didn’t cover edges ad or dg.
    2. It is neither. It is not a trail because it visits ab and be twice. Since it is not a trail, it cannot be an Euler trail.
    3. It is both. It is a trail because it is a walk that doesn’t cover any edges twice, and it is an Euler trail because it visits all the edges.

  2. Use the graph of a social network in to answer each question.

    1. Identify any bridges.
    2. If all bridges were removed, how many components would there be in the resulting graph?
    3. Identify one local bridge.
    4. For the local bridge you identified in part 3, identify the shortest path between the vertices of the local bridge if the local bridge were removed.
    Otkrij odgovor
    1. The edges ku, gh, and hi are bridges.
    2. If the bridges were all removed, there would be four components in the resulting graph, {i}, {h}, {u, v, w, x}, and {a, b, c, d, e, f, g, j, k, m, n, o, p, q, r, s, t} as shown in .
    3. Three local bridges are dn, ef, and qt, among others.
    4. If dn were removed, the shortest path between d and n would be d → e → f → j → o → m → n.

  3. Use Fleury’s Algorithm to find an Euler trail for Graph J in .

    Otkrij odgovor

    Step 1: Choose one of the two vertices of odd degree, c or f, as your starting vertex. We will choose c.

    Step 2: Remove edge ca, cb, or cd. None of these are cut edges so we can select any of the three. We will choose cb as shown in to be the first edge removed.

    Repeat Step 2 The next choice is to remove edge ba, bd, or bf as shown in , but bf is not an option since it is a bridge. We will choose ba as shown in to be the second edge removed.

    Repeat Step 2 for the third, fourth, fifth, sixth, and seventh edges. As shown in , until we get to the seventh edge there is only one option each time, ac, cd, db, and bf in that order. For the seventh edge, we must choose between fe and fg. Neither of these are bridges. We choose fe. shows that ac, cd, db, bf, and fe have been removed.

    Repeat Step 2 for the eight, ninth, tenth, and eleventh edges. As shown in , there is only one option for each of these edges, eh, hi, ig, and gf, in that order.

    Step 3: Write out the Euler trail using the vertices in the sequence that the edges were removed. We removed cb, ba, ac, cd, db, bf, fe, eh, hi, ig, and gf, in that order. The Euler trail is c → b → a → c → d → b → f → e → h → i → g → f.

  4. Use Fleury’s algorithm to find either an Euler circuit or Euler trail in Graph G in .

    Otkrij odgovor

    Graph G has all vertices of even degree so it has an Euler circuit.

    Step 1: Choose any vertex. We will choose vertex j.

    Step 2: Remove one of the four edges that meet at vertex j. Since jn is a bridge, we must remove either jh, ji, or jk. We remove ji as shown in .

    Repeat Step 2: Since id is a bridge, we can remove either ih or ik next. We remove ih, and then the only option is to remove hj as shown in .

    Repeat Step 2: Since jn is a bridge, the next edge removed must be jk, and then the only option is to remove ki followed by id as shown in . Even though id is a bridge, it can be removed because it is the only option at this point. shows Graph G with these additional edges removed.

    Repeat Step 2: Choose any one of the edges db, dc, or de. We remove dc as shown in .

    Repeat Step 2: Since co is a bridge, choose cb next. We remove cb, then bd, and then de as shown in .

    Repeat Step 2: Next, remove ec and co. Then choose any of op, pn, or om. We remove on as shown in .

    Repeat Step 2: Next, remove either nm, np, or nj, but nj is a So, we remove nm as shown in .

    Repeat Step 2: Next, remove mo, op, pn, and nj. And we are done!

    Step 3: Notice that the algorithm brought us back to the vertex where we started, forming an Euler circuit. Write out the Euler circuit:

    j → i → h → j → k → i → d → c → b → d → e → c → o → n → m → o → p → n → j

Symbols used here

y',\ y''
first and second derivative of y
Prime notation for derivatives with respect to x (or t).
i
imaginary unit
i² = −1.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
\prod_{k=1}^{n} a_k
product
Multiply a_k for k = 1 up to n.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.

How to: Euler Trails

  1. Describe and identify Euler trails.
  2. Solve applications using Euler trails theorem.
  3. Identify bridges in a graph.
  4. Apply Fleury’s algorithm.
  5. Evaluate Euler trails in real-world applications.
  6. It is a trail only. It is a trail because it is a walk that doesn’t cover any edges twice, but it is not an Euler trail because it didn’t cover edges
  7. It is neither. It is not a trail because it visits
  8. It is both. It is a trail because it is a walk that doesn’t cover any edges twice, and it is an Euler trail because it visits all the edges.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Pokušaj i ti

Parts of this page are adapted from OpenStax Contemporary Mathematics (CC BY-NC-SA 4.0). Condensed and re-explained here; errors are ours.

Više u Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs