Lecture 34 — Walks, Trails and Circuits

lecture
discrete-math
graph-theory

A recap of the graph theory so far (degree, the Handshake Theorem, the pigeonhole argument for equal degrees, complete graphs), then getting around a graph: walks, trails, circuits and connected graphs, and the theorem that says exactly when a graph has an Euler circuit, a circuit using every edge once, or an Euler trail. Pre-work: Video 044 (Walks, Trails and Circuits). Walks, trails, circuits and connectedness are in walks-trails-and-circuits. Euler circuits and trails, the theorem with its proof, how to find one, and the decision flowchart are in euler-circuits-and-trails. The basic definitions are in graphs.

Goals

  1. Understand the basic terminology and definitions of graph theory.
  2. Understand the conditions required for a graph to have an Euler circuit or trail.

Two questions to keep in mind:

  • What is the difference between an Euler circuit and an Euler trail? Both use every edge of the graph exactly once. An Euler circuit finishes at the vertex it started from; an Euler trail from \(u\) to \(v\) starts at \(u\) and finishes at a different vertex \(v\). For a connected graph the odd-degree vertices decide which one there is: none gives an Euler circuit, exactly two gives an Euler trail from one to the other, and more gives neither (the theorem).
  • How do I actually find an Euler circuit? First decide whether there is one, from the degrees and connectedness (the flowchart). Then build it by splicing: walk along unused edges until stuck, and while edges are left, take a vertex on the route that still has unused edges, walk a circuit from it, and insert that circuit into the route. It is done in full for an Euler trail on ten vertices, and the method, with why it always works, is in euler-circuits-and-trails.

The bridges of Königsberg

The city of Königsberg had four land masses, the north bank \(A\), the island \(B\), the south bank \(C\) and the eastern part \(D\), joined by seven bridges. Is there a walk around the city that crosses every bridge exactly once? As a graph, each land mass is a vertex and each bridge an edge. \(A\) and \(B\) are joined by two bridges, and so are \(B\) and \(C\), so the graph has multiple edges.

Figure 1: The bridges of Königsberg as a graph: land masses \(A\), \(B\), \(C\), \(D\) as vertices and the seven bridges as edges. Every vertex has odd degree, 3, 5, 3 and 3. An Euler circuit needs every degree even and an Euler trail needs exactly two odd degrees, so there is neither: no walk crosses every bridge exactly once.

The degrees are \(\deg A = 3\), \(\deg B = 5\), \(\deg C = 3\), \(\deg D = 3\), adding to \(14 = 2 \cdot 7\). A walk that crosses every bridge once and comes back is an Euler circuit, and one that finishes on a different land mass from where it started is an Euler trail. By the theorem below the first needs every degree even, and the second needs exactly two odd degrees. Here all four are odd, so neither exists. The problem is set up in 2026-07-27-welcome-and-intro-problems, where the land masses are lettered differently.

Recap: graphs, degree and the Handshake Theorem

All in graphs: a graph is a non-empty set of vertices and a possibly empty set of edges, each edge having one or two endpoints (graphs). A loop has one endpoint, multiple edges (parallel edges) share their endpoints, and a graph is simple if it has neither (graphs). The degree of a vertex is the number of edge ends at it, so a loop adds 2: a vertex with two ordinary edges and a loop has degree 4 (graphs). The Handshake Theorem: for a graph with vertices \(v_1, \dots, v_n\) and \(e\) edges, \[\sum_{i=1}^{n} \deg(v_i) = 2e,\] since every edge has two ends (graphs).

Two vertices of the same degree

Theorem. Any simple graph with at least two vertices has two vertices of the same degree.

Proof idea. With \(n\) vertices, a vertex of a simple graph has degree between \(0\) and \(n - 1\). Degrees \(0\) and \(n - 1\) cannot both occur: a vertex of degree \(n - 1\) is adjacent to every other vertex, so none has degree 0. So the degrees all lie in \(\{1, 2, \dots, n - 1\}\) or all lie in \(\{0, 1, \dots, n - 2\}\), at most \(n - 1\) values for \(n\) vertices, and by the pigeonhole principle two vertices share a degree.

For \(n = 6\): if some vertex has degree 5, the degrees are among \(1, 2, 3, 4, 5\); otherwise they are among \(0, 1, 2, 3, 4\). Five values either way, for six vertices. The full proof, with a figure, is in pigeonhole-principle.

Worked: counting with the Handshake Theorem

  1. A graph has 5 vertices with degree sequence 3, 3, 2, 2, 2. How many edges does the graph have?
  2. A graph has 6 vertices and 10 edges. If five of its vertices have degree 3, what is the degree of its other vertex?

(a) 6 edges. Let \(e\) be the number of edges. By the Handshake Theorem, \[3 + 3 + 2 + 2 + 2 = 2e, \qquad 12 = 2e, \qquad e = 6.\]

The degree sequence fixes the number of edges, but not the graph. A pentagon with one chord has these degrees and is simple. So does a graph made of three parallel edges between two vertices, two parallel edges between two more, and a loop at the fifth vertex, which is not simple. Both have 6 edges.

(b) Degree 5. Let \(x\) be the degree of the other vertex. By the Handshake Theorem, \[3 + 3 + 3 + 3 + 3 + x = 2 \cdot 10, \qquad 15 + x = 20, \qquad x = 5.\]

Such a graph exists: join one vertex to all five others, and join those five in a ring. Each ring vertex has its two ring neighbours and the centre, degree 3, and the centre has degree 5. That is \(5 + 5 = 10\) edges.

Figure 2: Graphs for the two counting questions, each vertex labelled with its degree. Left: a pentagon with one chord, a simple graph with degrees 3, 3, 2, 2, 2 and 6 edges. Middle: three parallel edges, two parallel edges and a loop, a non-simple graph with the same degrees and also 6 edges. The degree sequence fixes the number of edges, not the graph. Right: one vertex joined to the five vertices of a ring, 10 edges, with the centre of degree 5 and the other five of degree 3.

Complete graphs

In a simple graph there are no loops, and each pair of vertices is joined by at most one edge. There are \(\binom{n}{2}\) pairs of vertices, so a simple graph with \(n\) vertices has at most \(\binom{n}{2}\) edges.

The simple graph with \(n\) vertices and \(\binom{n}{2}\) edges is called the complete graph of order \(n\) and is denoted \(K_n\).

It joins every pair of vertices, so every vertex has degree \(n - 1\). More on these in graphs.

\(n\) 1 2 3 4 5 6 7
edges of \(K_n\), \(\binom n2\) 0 1 3 6 10 15 21
degree of each vertex 0 1 2 3 4 5 6

Figure 3: The complete graphs \(K_1\) to \(K_7\). Each joins every pair of its \(n\) vertices once, so it has \(\binom{n}{2}\) edges and every vertex has degree \(n - 1\). Lines cross where there is no vertex; only the dots are vertices.

Walks, trails and circuits

The definitions, in full with examples in walks-trails-and-circuits:

A walk is a sequence \(v_0\, e_1\, v_1\, e_2\, v_2 \cdots e_n\, v_n\) where each \(v_i\) is a vertex and each \(e_i\) is an edge with endpoints \(v_{i-1}\) and \(v_i\).
A trail is a walk where \(e_1, e_2, \dots, e_n\) are pairwise distinct.
A circuit is a trail \(v_0\, e_1\, v_1 \cdots e_n\, v_n\) where \(v_0 = v_n\).
A graph is connected if and only if there is a walk from any given vertex to any other given vertex.

A trail has no repeated edges, but it may repeat vertices. The route below is a trail that passes through one vertex twice.

Figure 4: A trail on a graph with two parallel edges at the top. The route, in red, starts at \(s\), goes from \(w\) to \(x\) along one of the parallel edges and back to \(w\) along the other, then goes down and right to finish at \(t\). It passes through \(w\) twice but uses no edge twice, since the two parallel edges are different edges, so it is a trail. It ends at \(t \ne s\), so it is not a circuit. It uses 7 of the 14 edges, so it is not an Euler trail either.

Worked: walks, trails and circuits in \(K_4\)

Determine whether the complete graph \(K_4\) contains the following:
(a) A walk that is not a trail.
(b) A trail that is not a circuit.
(c) An Euler circuit.

Label \(K_4\) with vertices \(v_1, v_2, v_3, v_4\) and edges \(e_1 = v_1v_2\), \(e_2 = v_2v_3\), \(e_3 = v_3v_4\), \(e_4 = v_1v_4\), \(e_5 = v_1v_3\), \(e_6 = v_2v_4\).

(a) Yes. \(v_4\, e_6\, v_2\, e_6\, v_4\, e_4\, v_1\). Each edge joins the vertices on either side of it, so it is a walk. It uses \(e_6\) twice, so it is not a trail.

(b) Yes. \(v_1\, e_4\, v_4\). A single edge is a trail, since no edge is repeated, and it ends at \(v_4 \ne v_1\), so it is not a circuit.

(c) No. \(K_4\) is connected, but every vertex has degree 3, which is odd, so by the theorem there is no Euler circuit. In fact there is no Euler trail either: that needs exactly two vertices of odd degree, and \(K_4\) has four.

Other answers work for (a) and (b). Any route that goes out and back along one edge answers (a), and any trail that ends somewhere other than its start answers (b), for example \(v_1\, e_1\, v_2\, e_2\, v_3\, e_5\, v_1\, e_4\, v_4\), which repeats \(v_1\) but no edge.

Figure 5: The three parts on \(K_4\). (a) The walk \(v_4,e_6,v_2,e_6,v_4,e_4,v_1\): the doubled red line is \(e_6\) used twice, so it is a walk but not a trail. (b) The trail \(v_1,e_4,v_4\): one edge, no repeats, and it ends at a different vertex from where it started. (c) Every vertex of \(K_4\) has degree 3, odd, so there is no Euler circuit, and with four odd vertices no Euler trail either.

Euler circuits and Euler trails

An Euler circuit is a circuit that contains every edge of the graph.
An Euler trail from vertex \(u\) to vertex \(v\) is a trail that starts at \(u\) and ends at \(v\) and contains every edge of the graph.

A graph with an Euler circuit is called Eulerian.

Theorem. Let \(G\) be a connected graph. Then \(G\) has an Euler circuit if and only if every vertex of \(G\) has even degree. Let \(u, v \in V(G)\) be distinct vertices of \(G\). Then \(G\) has an Euler trail from \(u\) to \(v\) if and only if \(u\) and \(v\) have odd degree and all other vertices of \(G\) have even degree.

Why the degrees. Each time a route passes through a vertex it arrives along one edge and leaves along another, using two edge ends there. If the route uses every edge exactly once, it uses every edge end at a vertex, so the degree is twice the number of passes, which is even. The exceptions are the start and the end: a trail from \(u\) to \(v \ne u\) leaves \(u\) once without having arrived and arrives at \(v\) once without leaving, so those two have odd degree. For a circuit the start and end are the same vertex and pair up. The other direction, that the right degrees guarantee an Euler circuit or trail when the graph is connected, is proved by building one, in euler-circuits-and-trails.

This course uses the standard definitions above. The textbook defines an Euler circuit as a circuit that contains every vertex and every edge. For connected graphs the two agree. In a connected graph with at least one edge every vertex is the endpoint of some edge, so a route using every edge passes through every vertex. A connected graph with no edges is a single vertex, and the trivial circuit there contains it. They differ when there are isolated vertices.

Figure 6: A square and an isolated vertex in the middle. Going once round the square, in red, is a circuit that contains every edge, so by this course’s definition the graph has an Euler circuit. By the textbook’s definition, which also asks for every vertex, it does not, since no circuit reaches the middle vertex.

More on the two definitions, with the proof that they agree for connected graphs, is in euler-circuits-and-trails.

Worked: which graphs have an Euler circuit or trail

For each of the following graphs, determine whether the graph has an Euler circuit. For those that do not contain an Euler circuit, determine whether the graph has an Euler trail.

Figure 7: The five graphs, each vertex labelled with its degree, odd degrees in red. \(G_1\) has two parallel edges at the top, and in \(G_4\) the bottom vertex has two parallel edges and a loop, which adds 2. \(G_1\) and \(G_4\) are connected with every degree even, so they have Euler circuits. \(G_2\) has exactly two odd vertices, so it has an Euler trail between them. \(G_3\) has four odd vertices, so it has neither. In \(G_5\) every degree is even, but the graph is two separate squares, since the crossings are not vertices, so it has neither.

Graph Degrees Connected? Odd vertices Verdict
\(G_1\) 2, 4, 4, 2 (top), 2, 4, 4, 2 (middle), 2, 2 (bottom) yes none Euler circuit
\(G_2\) 3, 2, 2, 2, 3 yes two no Euler circuit; Euler trail
\(G_3\) 5, 3, 3, 5, 4, 4 yes four neither
\(G_4\) 2, 2, 2, 4, 4 yes none Euler circuit
\(G_5\) 2 for all eight no none neither
  • \(G_1\). 14 edges, degrees adding to 28. Every degree is even and the graph is connected, so it has an Euler circuit. The two parallel edges at the top each count once at each end, which is why those two vertices have degree 4.
  • \(G_2\). A pentagon with a chord. The two ends of the chord have degree 3 and the rest degree 2. Exactly two odd vertices, so there is no Euler circuit, but there is an Euler trail from one end of the chord to the other: start at the top vertex, go all the way round the pentagon back to the top, then take the chord down.
  • \(G_3\). 12 edges. The top vertex and the centre each have degree 5, the left and right vertices degree 3, and the bottom two degree 4. Four odd vertices: no Euler circuit and no Euler trail.
  • \(G_4\). 7 edges: the square, the two parallel edges and the loop. The loop adds 2, so the bottom vertex has degree \(2 + 2 = 4\), and the square’s bottom-right corner has degree 4 too. All even and connected, so there is an Euler circuit: round the square, down one parallel edge, round the loop, back up the other.
  • \(G_5\). Every degree is 2, so the degrees alone would suggest an Euler circuit. But the lines cross at points that are not vertices, and the graph is two separate squares, an upright one and a tilted one. It is not connected, and a single route cannot use edges in both pieces, so there is no Euler circuit and no Euler trail. The theorem only applies to connected graphs.

Worked: an Euler trail from \(a\) to \(e\)

Use the theorem to show that the graph below has an Euler trail from \(a\) to \(e\), and find one.

The graph has 21 edges: \(ab\), \(ah\), \(ai\), \(bc\), \(bd\), \(bh\), \(cd\), \(cf\), \(ci\), \(de\), \(df\), \(ef\), \(fg\), \(fi\), \(fj\), \(gh\), \(gi\), \(gj\), \(hi\), \(ij\), \(je\). The graph is simple, so a route can be written as a list of vertices.

Vertex \(a\) \(b\) \(c\) \(d\) \(e\) \(f\) \(g\) \(h\) \(i\) \(j\)
Degree 3 4 4 4 3 6 4 4 6 4

The degrees add to \(42 = 2 \cdot 21\). Vertices \(a\) and \(e\) have odd degree, all other vertices have even degree, and the graph is connected, so by the theorem it has an Euler trail from \(a\) to \(e\).

Figure 8: The graph on \(a\) to \(j\), each vertex labelled with its degree. Only \(a\) and \(e\), in red, have odd degree, and the graph is connected, so there is an Euler trail from \(a\) to \(e\) and no Euler circuit. Lines cross at several points that are not vertices.

Finding one by splicing. Start at \(a\), one of the two odd vertices, and walk along unused edges until stuck:

\[a,\ b,\ c,\ d,\ e,\ f,\ j,\ e.\]

At \(e\) all three edges are now used, so this is stuck, at \(e\) as it must be. It uses 7 of the 21 edges. The 14 unused edges give every vertex even degree, and \(j\) is on the route and still has unused edges (\(ji\) and \(jg\)). Walk from \(j\) along unused edges until stuck, which brings it back to \(j\):

\[j,\ i,\ c,\ f,\ i,\ a,\ h,\ i,\ g,\ h,\ b,\ d,\ f,\ g,\ j.\]

That uses the other 14 edges. Insert it into the first route at \(j\):

\[a,\ b,\ c,\ d,\ e,\ f,\ \underbrace{j,\ i,\ c,\ f,\ i,\ a,\ h,\ i,\ g,\ h,\ b,\ d,\ f,\ g,\ j}_{\text{inserted}},\ e.\]

This is an Euler trail from \(a\) to \(e\): 21 edges, each of the 21 exactly once, starting at \(a\) and ending at \(e\). It passes through \(f\) and \(i\) three times each, using all six edges at each.

Figure 9: The Euler trail from \(a\) to \(e\), with each edge numbered in the order the trail uses it. Red: the first walk from \(a\), which gets stuck at \(e\) after 7 edges. Blue: the circuit from \(j\) through the 14 unused edges, inserted into the first walk at \(j\), between edges 6 and 21. Following the numbers 1 to 21 gives \(a,b,c,d,e,f,j,i,c,f,i,a,h,i,g,h,b,d,f,g,j,e\).

The trail is not unique. Walking differently until stuck, or inserting at a different vertex, gives other Euler trails from \(a\) to \(e\), and reversing any of them gives an Euler trail from \(e\) to \(a\).

Deciding: the flowchart

How to tell whether a graph has an Euler circuit, connected or not:

Figure 10: Deciding whether a graph has an Euler circuit, with an example graph at each outcome. No edges: the trivial circuit counts, as for three isolated vertices. Otherwise delete the isolated vertices and check that what is left is connected. A square and a triangle that only cross in the drawing are two pieces, so there is no Euler circuit even though every degree is even. Then check the degrees: the eight-vertex graph has degrees 2 and 4 and has an Euler circuit, while the square with one diagonal has two vertices of degree 3, so it has no Euler circuit but does have an Euler trail.

Each step, in words:

  1. No edges at all. Then there is an Euler circuit: the trivial circuit, a single vertex, contains every edge, since there are none.
  2. Delete the isolated vertices. A route never needs to visit a vertex with no edges, and this course’s definition only asks for every edge.
  3. Not connected. Two edges in different pieces cannot be on one route, so there is no Euler circuit, and no Euler trail either.
  4. Connected. The theorem decides: every degree even gives an Euler circuit. Otherwise there is no Euler circuit, and if there are exactly two vertices of odd degree, there is an Euler trail from one to the other.

A version that also sorts out the Euler trail case completely, with why each step is right, is in euler-circuits-and-trails.

See also