Euler Trails and Circuits

Section 2.4 Euler Trails and Circuits

Objectives

After completing this section, you should be able to do the following.

Identify whether a graph or multigraph has an Euler trail or circuit.
Justify why the necessary condition for a graph having an Euler trail is necessary.
Distinguish between Euler trails and Hamilton paths, and decide which is more appropriate to use for a given problem.

Subsection Section Preview

Investigate!

A spider is standing on one face of an octahedron (a polyhedron with eight triangular faces). She wants to crawl along the solid from face to face so that she crosses each edge exactly once. Is this possible? If so, how?

🔗

$An octahedron$

🔗

If we start at a vertex and trace along edges to get to other vertices, we create a walk through the graph. More precisely, a walk in a graph is a sequence of vertices such that every vertex in the sequence is adjacent to the vertices before and after it in the sequence. If the walk travels along every edge exactly once, then the walk is called an Euler trail (or Euler walk or Euler path). If, in addition, the starting and ending vertices are the same (so you trace along every edge exactly once and end up where you started), then the walk is called an Euler circuit (or Euler tour). Of course if a graph is not connected, there is no hope of finding such a trail or circuit. For the rest of this section, assume all the graphs discussed are connected.

🔗

The bridges of Königsberg problem is really a question about the existence of Euler trails. There will be a route that crosses every bridge exactly once if and only if the multigraph below has an Euler trail:

🔗

$Three vertices aligned in a vertical column left of a single vertex on the right. Edges connect the vertex on the right to each vertex on the left. Among the vertices on the left, two arced edges connect the bottom vertex to the center vertex, and two more connect the center vertex to the top vertex.$

This graph is small enough that we could actually check every possible walk that does not reuse edges, and in doing so convince ourselves that there is no Euler trail (let alone an Euler circuit). On small graphs that do have an Euler trail, it is usually not difficult to find one. Our goal is to find a quick way to check whether a graph has an Euler trail or circuit, even if the graph is quite large.

🔗

Worksheet Preview Activity
A4 US

Which of the graphs below have an Euler trail? Which have an Euler circuit?

🔗

$A tree with 7 vertices an 6 edges. The bottom vertex has degree 2, leading to two vertices in the middle with degree 3, each leading to a leaf$

$A graph consisting of 6 vertices and 10 edges$

$A graph with 7 vertices and 9 edges$

G_{1}

🔗

G_{2}

🔗

G_{3}

🔗

$A graph with six vertices. Four vertices form a square, with another vertex centered inside the square, and the last vertex centered above the square. Edges connect the corners of the square, and connect each corner to the center vertex. The top two vertices of the square is adjacent to the vertex above the square.$

$A graph with seven vertices. Four vertices form the corners of a square, the remaining three are in a middle row, with one to the left, one in the center, and one to the right of the square. Edges form the sides of the square. Each vertex in the square is adjacent to the two middle-row vertices closest to it.$

$A graph with 8 vertices and 12 edges, representing a cube.$

G_{4}

🔗

G_{5}

🔗

G_{6}

🔗

1.

G_{1}

has

🔗

an Euler trail
an Euler circuit and trail
Neither

G_{2}

has

🔗

an Euler trail
an Euler circuit and trail
Neither

G_{3}

has

🔗

an Euler trail
an Euler circuit and trail
Neither

🔗

G_{4}

has

🔗

an Euler trail
an Euler circuit and trail
Neither

G_{5}

has

🔗

an Euler trail
an Euler circuit and trail
Neither

G_{6}

has

🔗

an Euler trail
an Euler circuit and trail
Neither

🔗

2.

Write down the degree sequence of the graphs above.

🔗

G_{1} :

🔗

G_{2} :

🔗

G_{3} :

🔗

G_{4} :

🔗

G_{5} :

🔗

G_{6} :

🔗

What might the connection be between the degree sequence and the existence of an Euler trail or circuit?

🔗

3.

One way to write down an Euler trail or circuit is to list the edges in order. Each edge will be a pair of vertices, and to indicate what direction we travel over that edge, we can write it as an ordered pair rather than a set. For example, consider this graph:

🔗

a path of 4 vertices labeled a, b, c, d connected in that order by three edges.

There are two Euler trails we could write:

🔗

(a, b), (b, c), (c, d) or (d, c), (c, b), (b, a) .

🔗

(a)

Write down an Euler trail for the graph below.

🔗

a graph with 6 vertices labeled a through f. Vertices a and f have degree one and are drawn on the far left and right respectively. The other vertices form a diamond. edges: (a,b), (b,c), (b,e), (b,d), (c,e), (d,e) and (e,f).

For each vertex, write down its degree and the number of times it appears in your list of edges.

🔗

vertex	degree	times listed
$a$
$b$
$c$
$d$
$e$
$f$

(b)

Suppose you have a graph with degree sequence

(4, 2, 2, 2, 2)

that has an Euler trail. How many times will the name of the degree 4 vertex appear in your list of edges?

🔗

(c)

Suppose you have a graph with an Euler trail written as a list of edges. What can you conclude about a vertex that appears exactly 3 times in the list? Select all the choices that could be true.

🔗

The vertex could appear at the start and end of the Euler trail.
The vertex could appear at the start or end of the Euler trail, but not both.
The vertex could appear only in the middle of the Euler trail.
The vertex cannot appear in the Euler trail at all.
There must be another vertex with odd degree that also appears at the start or end of the Euler trail.

🔗

Subsection Conditions for Euler Trails

One way to guarantee that a graph does not have an Euler circuit is to include a “spike,” a vertex of degree 1.

🔗

$Three vertices in a triangle (with edges connecting them), plus a 4th vertex labeled a adjacent to one of the others.$

The vertex

a

has degree 1, and if you try to make an Euler circuit, you see that you will get stuck at the vertex. It is a dead end. That is, unless you start there. But then there is no way to return, so there is no hope of finding an Euler circuit. There is however an Euler trail. It starts at the vertex

a,

then loops around the triangle. You will end at the vertex of degree 3.

🔗

You run into a similar problem whenever you have a vertex of any odd degree. If you start at such a vertex, you will not be able to end there (after traversing every edge exactly once). After using one edge to leave the starting vertex, you will be left with an even number of edges emanating from the vertex. Half of these could be used for returning to the vertex, the other half for leaving. So you return, then leave. Return, then leave. The only way to use up all the edges is to use the last one by leaving the vertex. On the other hand, if you have a vertex with odd degree at which you do not start a trail, then you will eventually get stuck at that vertex. The trail will use pairs of edges incident to the vertex to arrive and leave again. Eventually all but one of these edges will be used up, leaving only an edge to arrive by, and none to leave again.

🔗

What all this says is that if a graph has an Euler trail and two vertices with odd degree, then the Euler trail must start at one of the odd-degree vertices and end at the other. In such a situation, every other vertex must have an even degree since we need an equal number of edges to get to those vertices as to leave them. How could we have an Euler circuit? The graph could not have any odd-degree vertex as an Euler trail would have to start there or end there, but not both. Thus for a graph to have an Euler circuit, all vertices must have even degree.

🔗

The converse is also true: if all the vertices of a graph have even degree, then the graph has an Euler circuit, and if there are exactly two vertices with odd degree, the graph has an Euler trail. To prove this is a little tricky, but the basic idea is that you will never get stuck because there is an “outbound” edge for every “inbound” edge at every vertex. If you try to make an Euler trail and miss some edges, you will always be able to “splice in” a circuit using the edges you previously missed.

🔗

Euler Trails and Circuits.

A graph has an Euler circuit if and only if the degree of every vertex is even.
A graph has an Euler trail if and only if there are at most two vertices with odd degree.

🔗

Since the bridges of Königsberg graph has all four vertices with odd degree, there is no Euler trail through the graph. Thus there is no way for the townspeople to cross every bridge exactly once.

🔗

Subsection Hamilton Paths

Suppose you wanted to tour Königsberg in such a way that you visit each land mass (the two islands and both banks) exactly once. This can be done. In graph theory terms, we are asking whether there is a path that visits every vertex exactly once. Such a path is called a Hamilton path (or Hamiltonian path). We could also consider Hamilton cycles, which are Hamilton paths that start and stop at the same vertex.

🔗

Example 2.4.1.

Determine whether the graphs below have a Hamilton path.

🔗

$The Petersen graph: ten vertices arranged in two rings of five each. Each outer vertex is adjacent to the two outer vertices closest to it, forming a pentagon, and to the inner vertex closest to it. Each inner vertex is adjacent to the two inner vertices not neighboring it, forming a 5-ponted star.$

$A graph with ten vertices. Five vertices form a copy of K5, the complete graph in which each vertex is adjacent to the other four. The remaining five vertices are each adjacent to only one of the five vertices in the copy of K5.$

Solution.

The graph on the left has a Hamilton path (many different ones, actually), as shown here:

$The Petersen graph with a highlighted path visiting every vertex exactly once. The path starts at the top outer vertex, proceeds down and two the left to the bottom-left outer vertex, then to the top-left outer vertex, then in and across to the top-right outer vertex, and finally down to the bottom-left outer vertex and up to the bottom-left inner vertex.$

The graph on the right does not have a Hamilton path. You would need to visit each of the “outside” vertices, but as soon as you visit one, you get stuck. Note that this graph does not have an Euler trail, although there are graphs with Euler trails but no Hamilton paths.

🔗

It appears that finding Hamilton paths would be easier because graphs often have more edges than vertices, so there are fewer requirements to be met. However, nobody knows whether this is true. There is no known simple test for whether a graph has a Hamilton path. For small graphs this is not a problem, but as the size of the graph grows, it gets harder and harder to check whether there is a Hamilton path. In fact, this is an example of a question which as far as we know is too difficult for computers to solve in general, as it is an example of a problem that is NP-complete.

🔗

Reading Questions Reading Questions

1.

Is there a graph that has an Euler circuit but not an Euler trail? Explain your answer.

🔗

2.

Can a tree have an Euler tour? Can a tree have an Euler circuit? Explain your answers.

🔗

3.

What questions do you have after reading this section? Write at least one question about the content of this section that you are curious about.

🔗

Exercises Practice Problems

1.

Consider the graph given above. Give an Euler trail through the graph by listing the vertices in the order visited.

🔗

2.

Which of the following graphs have Euler circuits?

🔗


A: Has Euler circuit.	B: Has Euler circuit.


C: Has Euler circuit.	D: Has Euler circuit.

🔗

3.

Which of the following graphs have Euler circuits or Euler trails?

🔗


A: Has Euler trail.	B: Has Euler trail.
A: Has Euler circuit.	B: Has Euler circuit.


C: Has Euler trail.	D: Has Euler trail.
C: Has Euler circuit.	D: Has Euler circuit.

🔗

4.

Consider the graph given above. Add an edge so the resulting graph has an Euler trail (without repeating an existing edge).

🔗

Now give an Euler trail through the graph with this new edge by listing the vertices in the order visited.

🔗

Exercises Additional Exercises

1.

You and your friends want to tour the southwest by car. You will visit the nine states below, with the following rather odd rule: You must cross each border between neighboring states exactly once (so, for example, you must cross the Colorado-Utah border exactly once). Can you do it? If so, does it matter where you start your road trip? What fact about graph theory solves this problem?

🔗

$A map of the United States, with Southwest states highlighted.$

🔗

2.

Which of the following graphs contain an Euler trail? Which contain an Euler circuit?

🔗

$K_{4}$
$K_{5}$
$K_{5, 7}$
$K_{2, 7}$
$C_{7}$
$P_{7}$

🔗

3.

Edward A. Mouse has just finished his brand new house. The floor plan is shown below:

🔗

$A rectangle subdivided into seven smaller rectangles, with three on top, and four below. The top-left rectangle has gaps leading to the top-middle and bottom-left rectangles. The top-middle rectangle also has gaps to the two bottom-middle rectangles and the top-right rectangle. The top-right rectangle has gaps leading to the bottom-right rectangle and the bottom-middle-right rectangle. The bottom rectangles have gaps leading to the bottom rectangles adjacent to them.$

Edward wants to give a tour of his new pad to a lady-mouse friend. Is it possible for them to walk through every doorway exactly once? If so, in which rooms must they begin and end the tour? Explain.
Is it possible to tour the house visiting each room exactly once (not necessarily using every doorway)? Explain.
After a few mouse-years, Edward decides to remodel. He would like to add some new doors between the rooms he has. Of course, he cannot add any doors to the exterior of the house. Is it possible for each room to have an odd number of doors? Explain.

🔗

4.

For which

n

does the graph

K_{n}

contain an Euler circuit? Explain.

🔗

5.

For which

m

and

n

does the graph

K_{m, n}

contain an Euler trail? An Euler circuit? Explain.

🔗

6.

For which

n

does

K_{n}

contain a Hamilton path? A Hamilton cycle? Explain.

🔗

7.

For which

m

and

n

does the graph

K_{m, n}

contain a Hamilton path? A Hamilton cycle? Explain.

🔗

Hint.

This is harder than the previous three questions. Think about which “side” of the graph the Hamilton path would need to be on at every other step.

🔗

8.

A bridge builder has come to Königsberg and would like to add bridges so that it is possible to travel over every bridge exactly once. How many bridges must be built?

🔗

9.

Below is a graph representing friendships between a group of students (each vertex is a student and each edge is a friendship). Is it possible for the students to sit around a round table in such a way that every student sits between two friends? What does this question have to do with trails?

🔗

$A complicated graph containing 9 vertices arranged in a circle. If we call the vertex at the top of the circle 1, and number them proceeding clockwise, then vertex 1 is adjacent to 2, 4, 6, and 7. Vertex 2 is also adjacent to 4 and 7. Vertex 3 is adjacent to 6 and 8. Vertex 4 is adjacent to 6, 7, 8, and 9. Vertex 5 is adjacent to 6, 8, and 9. Vertex 7 is also adjacent to 8.$

Hint.

If you read off the names of the students in order, you would need to read each student’s name exactly once, and the last name would need to be of a student who was friends with the first. What sort of a cycle is this?

🔗

10.

On the table rest 8 dominoes, as shown below. If you were to line them up in a single row, so that any two sides touching had matching numbers, what would the sum of the two end numbers be?

🔗

$A domino with two dots and four dots.$

$A domino with six dots and two dots.$

$A domino with one dot and three dots.$

$A domino with four dots and six dots.$

$A domino with five dots and three dots.$

$A domino with four dots and three dots.$

$A domino with six dots and five dots.$

$A domino with three dots and six dots.$

Hint.

Draw a graph with 6 vertices and 8 edges. What sort of walk would be appropriate?

🔗

11.

Is there anything we can say about whether a graph has a Hamilton path based on the degrees of its vertices?

🔗

Suppose a graph has a Hamilton path. What is the maximum number of vertices of degree one the graph can have? Explain why your answer is correct.
Find a graph that does not have a Hamilton path even though no vertex has degree one. Explain why your example works.

🔗

12.

Consider the following graph:

🔗

$A graph with 11 vertices. Eight of these are arranged in a circle and with eight edges form the border of an octagon. The other three vertices are in a horizontal row in the center of the octagon. Edges connect the top and bottom vertices of the octagon to the left and right inner vertices. The left outer vertex is adjacent to the inner left vertex, and the right outer vertex is adjacent to the inner right vertex. The remaining four vertices of the octagon are adjacent to the center vertex.$

Find a Hamilton path. Can your path be extended to a Hamilton cycle?
Is the graph bipartite? If so, how many vertices are in each “part”?
Use your answer to part (b) to prove that the graph has no Hamilton cycle.
Suppose you have a bipartite graph $G$ in which one part has at least two more vertices than the other. Prove that $G$ does not have a Hamilton path.

🔗

You have attempted 1 of 11 activities on this page.

🔗

Prev Top Next

Section 2.4 Euler Trails and Circuits

Objectives

Subsection Section Preview

Investigate!

Worksheet Preview Activity A4US

1.

2.

3.

(a)

(b)

(c)

Subsection Conditions for Euler Trails

Euler Trails and Circuits.

Subsection Hamilton Paths

Example 2.4.1.

Reading Questions Reading Questions

1.

2.

3.

Exercises Practice Problems

1.

2.

3.

4.

Exercises Additional Exercises

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

Worksheet Preview Activity
A4 US