Which of the graphs below have an Euler trail? Which have an Euler circuit?
\begin{equation*}
G_1
\end{equation*}
\begin{equation*}
G_2
\end{equation*}
\begin{equation*}
G_3
\end{equation*}
\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:
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.