Skip to main content
Logo image

Discrete Mathematics: An Open Introduction, 4th edition

Oscar Levin

Worksheet Preview Activity
A4US

Which of the graphs below have an Euler trail? Which have an Euler circuit?
A graph
\begin{equation*} G_1 \end{equation*}
\begin{equation*} G_2 \end{equation*}
\begin{equation*} G_3 \end{equation*}
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 drawing of a cube
\begin{equation*} G_4 \end{equation*}
\begin{equation*} G_5 \end{equation*}
\begin{equation*} G_6 \end{equation*}
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\text{:}\)
\(G_2\text{:}\)
\(G_3\text{:}\)
\(G_4\text{:}\)
\(G_5\text{:}\)
\(G_6\text{:}\)
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 short path
There are two Euler trails we could write:
\begin{equation*} (a,b), (b,c), (c,d) \qquad \text{or} \qquad (d,c), (c,b), (b,a) \text{.} \end{equation*}
(a)
Write down an Euler trail for the graph below.
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.
PrevTopNext