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 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
\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 graph with 8 vertices and 12 edges, representing 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 path of 4 vertices labeled a, b, c, d connected in that order by three edges.
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.
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.
PrevTopNext
Feedback