Edge Use and Vertex Repetition
Eulerian questions concern how edges are used. A route may revisit a vertex and still be a trail, but it may not traverse an edge twice. An Euler trail adds a further requirement: it must use every edge of the graph. Keeping these conditions separate prevents a common confusion between trails and paths, and between closed trails and cycles.
Unless stated otherwise, graphs here are finite and simple. In an undirected graph, an edge \(uv\) can be traversed from \(u\) to \(v\) or from \(v\) to \(u\). A directed graph, or digraph, has directed edges called arcs; an arc \((u,v)\) can be traversed only from \(u\) to \(v\). For a digraph, the arc set consists of ordered pairs, and both \((u,v)\) and \((v,u)\) may be present as distinct arcs.
A trail may repeat vertices. What it cannot repeat is an edge. A path has no repeated vertices, while a cycle is a closed walk of length at least \(3\) whose vertices are distinct except for the equality of the first and last vertices. Thus a cycle is a closed trail, but a closed trail need not be a cycle: it may revisit an internal vertex.
Some books use “circuit” specifically for a closed trail and reserve “cycle” for a closed trail with no repeated vertices apart from its endpoints. We use that distinction here. In particular, an Euler circuit can repeat vertices and need not be a cycle.
We adopt the following convention for graphs with no edges. If \(V\ne\varnothing\) and \(E=\varnothing\), a length-zero trail consisting of any single vertex uses every edge exactly once, since there are no edges to use; it is therefore an Euler trail and an Euler circuit. If \(V=\varnothing\), there is no vertex sequence to serve as a trail, so there is no Euler trail under this convention. When \(E\ne\varnothing\), an Euler trail necessarily has positive length.
Basic Consequences of the Definitions
Proof. Let \(v_0,v_1,\dots,v_\ell\) be the vertex sequence of an undirected trail. Its reversed sequence is \(v_\ell,v_{\ell-1},\dots,v_0\). Each consecutive pair in the reversed sequence is adjacent because the corresponding pair was adjacent in the original sequence and undirected edges can be traversed either way. The reversed sequence uses exactly the original edges, each once, so it is a trail. In a digraph, reversing a step along \((u,v)\) would require an arc \((v,u)\), which need not exist. \(\square\)
Proof. Write the closed trail as \(v_0,v_1,\dots,v_\ell\), where \(v_0=v_\ell\) and \(\ell\ge1\). Among all pairs of indices \(i<j\) with \(v_i=v_j\), choose one for which \(j-i\) is as small as possible. The segment \(v_i,v_{i+1},\dots,v_j\) is a closed walk of positive length. None of its interior vertices can repeat: such a repetition would give a pair of equal vertices with a smaller index difference. Its length cannot be \(1\), because the graph has no loops. Its length cannot be \(2\), because in a simple undirected graph the two steps would traverse the same edge twice, contrary to the trail condition. Therefore its length is at least \(3\); its vertices are distinct except for its equal endpoints, so this segment is a cycle. \(\square\)
Proof. A trail uses each of its edges at most once, and its length is the number of edges it uses. An Euler trail uses every one of the \(m\) edges exactly once, so its length is \(m\). The same count applies to arcs in a digraph. When there are no edges, the stated length is \(0=|E|\), in agreement with the zero-length convention. \(\square\)
Worked Examples
Worked Example: A Walk That Repeats an Edge
Let \(G=(V,E)\) be the undirected graph with \(V=\{1,2,3\}\) and \(E=\{12,23\}\). Consider the sequence \(1,2,3,2\).
The consecutive steps are \(1\) to \(2\), \(2\) to \(3\), and \(3\) to \(2\). Their edges, in order, are \(12,23,23\). The sequence is a walk of length \(3\), and it repeats vertex \(2\). It is not a trail, because it traverses edge \(23\) twice. The graph has \(2\) edges, but the walk has length \(3\), so it cannot be an Euler trail either.
Check: Listing the edge sequence gives \(12,23,23\); the repeated edge \(23\) directly violates the definition of a trail. Listing the graph’s edge set gives \(12,23\), so using every edge once would require a trail of length \(2\), not \(3\).
Worked Example: A Trail That Repeats Vertices
Let \(G=(V,E)\) have \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,ca,ad,dc\}\). Consider the sequence \(a,b,c,a,d,c\).
The consecutive edges are \(ab,bc,ca,ad,dc\), in that order. They are five distinct edges, so this is a trail of length \(5\). It repeats vertices: \(a\) occurs at the first and fourth positions, and \(c\) occurs at the third and sixth positions. It is therefore not a path. It is not closed, since it starts at \(a\) and ends at \(c\). But it is an Euler trail: the listed edge sequence contains all five edges of \(G\), each exactly once.
Check: The edge set has \(5\) members, and the trail has length \(5\). Comparing the two lists, \(\{ab,bc,ca,ad,dc\}=E\), confirms that every edge appears once. The unequal endpoints \(a\) and \(c\) confirm that this Euler trail is not an Euler circuit.
Worked Example: An Euler Circuit in an Undirected Graph
Let \(G=(V,E)\) have \(V=\{1,2,3\}\) and \(E=\{12,23,31\}\). The sequence \(1,2,3,1\) uses the edges \(12,23,31\), respectively. Each of the three edges appears once, and the sequence starts and ends at \(1\). Thus it is an Euler circuit.
This example is also a cycle, because its vertices are distinct except for the agreement of the first and last vertex. Not every Euler circuit must be a cycle; a closed trail may revisit other vertices as well.
Check: The graph has \(3\) edges, and the sequence has \(3\) steps, so its length is \(3=|E|\). The step-by-step edge list \(12,23,31\) agrees with \(E\) and has no repetition.
Worked Example: Following Arc Directions
Let \(D\) be the digraph with \(V=\{p,q,r,s\}\) and arc set \(A=\{(p,q),(q,r),(r,p),(p,s)\}\). The sequence \(p,q,r,p,s\) follows arcs \((p,q),(q,r),(r,p),(p,s)\), in that order.
The four arcs are distinct and the sequence uses every arc, so it is an Euler trail. It is open: it starts at \(p\) and ends at \(s\). The reverse sequence \(s,p,r,q,p\) is not a directed trail, because its first step would require the arc \((s,p)\), which is not in \(A\). An undirected trail can always be reversed, but a directed trail generally cannot.
Check: The arc set has \(4\) members, and the sequence has \(4\) steps. Its listed arcs are exactly \((p,q),(q,r),(r,p),(p,s)\), each once. The reverse sequence requires \((s,p)\) as its first arc, and \((s,p)\notin A\).
Worked Example: A Directed Euler Circuit
Let \(D\) have \(V=\{x,y,z\}\) and arc set \(A=\{(x,y),(y,z),(z,x)\}\). The sequence \(x,y,z,x\) follows the three arcs in order, uses each exactly once, and ends where it began. It is therefore an Euler circuit in the digraph.
Check: There are \(3\) arcs, and the sequence has \(3\) steps. Its arc list matches the entire set \(A\) without repetition, and its first and last vertices are both \(x\).
Conventions to Keep Separate
| Term | Must use edges or arcs only once? | May repeat vertices? | Must use every edge or arc? | Must end where it starts? |
|---|---|---|---|---|
| Walk | No | Yes | No | No |
| Trail | Yes | Yes | No | No |
| Closed trail (circuit) | Yes | Yes | No | Yes |
| Euler trail | Yes | Yes | Yes | No |
| Euler circuit | Yes | Yes | Yes | Yes |
For a digraph, “edge” in the table means directed arc, and every step must follow the arc direction. The requirement that every edge be used belongs to the word Euler; it is not part of the definition of a trail by itself. A trail can use only some of the edges of a graph, as long as it does not repeat any of them.
Common Pitfall
Wrong calculation: In the graph from the second worked example, the sequence \(a,b,c,a,d,c\) repeats \(a\) and \(c\), so it is not a trail. This conclusion mistakenly applies the no-repeated-vertices rule for a path to a trail.
Correction: Check the edges, not just the vertices. The edge sequence is \(ab,bc,ca,ad,dc\), with no repeated edge. Therefore the sequence is a trail, and because those are all five edges of the graph, it is an Euler trail. Repeated vertices prevent it from being a path, but do not prevent it from being a trail or Euler trail.
A second useful check is to distinguish “closed” from “Euler.” A closed trail returns to its starting vertex, but may leave some edges unused. An Euler trail uses every edge, but need not return to its starting vertex. Both properties are required for an Euler circuit.
Check Your Understanding
For each question, track the sequence of edges or arcs as well as the vertices.
- In the graph with \(V=\{1,2,3\}\) and \(E=\{12,23,31\}\), is the sequence \(1,2,3,1,2\) a walk, a trail, or an Euler trail? Explain.
- Give an example of a closed trail that is not a cycle, or explain why your example meets both definitions.
- In the digraph with arcs \((u,v)\), \((v,w)\), and \((w,u)\), is \(u,w,v,u\) a directed trail? Why or why not?
- If a graph has \(7\) edges, what must be the length of any Euler trail in it? State the definition that justifies your answer.
- Under the convention in this tutorial, does a graph with one vertex and no edges have an Euler circuit? What about a graph with no vertices and no edges?