Connectedness, Euler Trails and Circuits
Theory
An Eulerian trail uses every edge of a connected network exactly once; an Eulerian circuit does the same and finishes where it started. Count the odd vertices: \(0\) means a circuit, \(2\) means a trail between them, anything else means neither. This Year 10A maths page also covers the bridges of Königsberg, adding edges, pencil strokes and the shortest route that covers every edge.
A network (or graph) is a set of vertices joined by edges. The degree of a vertex is the number of edge ends at it; a loop counts \(2\). A network is connected if there is a route between every pair of vertices.
A trail is a walk that never repeats an edge. An Eulerian trail uses every edge exactly once. An Eulerian circuit is an Eulerian trail that starts and finishes at the same vertex.
Euler's rule (connected networks): if every vertex is even, there is an Eulerian circuit, and it can start anywhere. If exactly two vertices are odd, there is an Eulerian trail; it must start at one odd vertex and finish at the other. With \(4\), \(6\), \(\ldots\) odd vertices there is neither.
Euler found this rule in 1736 when he showed that no walk could cross each of the seven bridges of Königsberg exactly once: the land areas, as vertices, had four odd degrees.
Eulerian trails and circuits model real tasks where every link must be covered once: a mail or garbage truck driving every street, a council inspector walking every footpath, or a tourist crossing every bridge.
So the number of odd vertices is always even. Euler's rule for a connected network:
| Odd vertices | Eulerian circuit? | Eulerian trail? |
|---|---|---|
| \(0\) | yes, from any vertex | yes (the circuit itself) |
| \(2\) | no | yes, from one odd vertex to the other |
| \(4, 6, 8, \ldots\) | no | no |
Deciding and writing a trail or circuit
- Check the network is connected.
- Find the degree of every vertex. From a table of edges, add along each row; a loop counts \(2\).
- Count the odd vertices and apply Euler's rule.
- Write the route: start at an odd vertex (any vertex for a circuit). Cross off each edge as you use it. Do not use an edge that would cut you off from edges you have not used yet.
- Check the route has as many steps as the network has edges, with no edge repeated.
Other question types
- Is this route Eulerian? Check every step is an edge, that no edge is repeated and that no edge is missed. Count them.
- Modelling: make each land area, room or intersection a vertex and each bridge, door or street an edge. Two bridges between the same places are two edges.
- Adding or closing an edge changes the degree of both of its ends by \(1\). To get a circuit, new edges must join the odd vertices in pairs (Example 2).
- A degree in terms of \(m\): write each degree as an expression, then ask when it is even or odd.
- Repeating edges (inspection routes): repeat the shortest route between the two odd vertices; with four odd vertices, try all three pairings and take the smallest.
- Explaining the rule: a trail arrives at and leaves a middle vertex in pairs of edges, so middle vertices are even; the first edge at the start and the last edge at the finish are unpaired.
(i) find the degree of each vertex
(ii) decide whether it has an Eulerian circuit, an Eulerian trail or neither
(iii) write one.
(i) \(\deg A = 4\), \(\deg B = 3\), \(\deg C = 3\), \(\deg D = 4\), \(\deg E = 2\). Check: the sum is \(16 = 2\times 8\) edges.
(ii) The network is connected and has exactly two odd vertices, \(B\) and \(C\). So it has an Eulerian trail from \(B\) to \(C\) (or \(C\) to \(B\)), but no Eulerian circuit.
(iii) Start at an odd vertex and tick off edges as you go:
B – A – C – D – E – A – D – B – C
Check: \(BA, AC, CD, DE, EA, AD, DB, BC\) are \(8\) different edges, which is every edge, and the trail finishes at the other odd vertex. Other trails are possible.
(i) Explain why the network has no Eulerian trail.
(ii) One new edge is added between \(A\) and \(C\). Where must an Eulerian trail now start and finish?
(iii) What is the smallest number of new edges that gives an Eulerian circuit?
(i) \(A\), \(B\), \(C\) and \(D\) each have degree \(3\) and \(O\) has degree \(4\). That is four odd vertices, but a trail can have at most two.
(ii) A new edge adds \(1\) to the degree of each of its ends. \(A\) and \(C\) become \(4\), so only \(B\) and \(D\) are odd. The trail must start at \(\boldsymbol{B}\) and finish at \(\boldsymbol{D}\), or the reverse, for example \(B\)–\(A\)–\(O\)–\(B\)–\(C\)–\(O\)–\(D\)–\(A\)–\(C\)–\(D\).
(iii) Each new edge can make at most two odd vertices even. Four odd vertices need at least \(\mathbf{2}\) new edges, and \(AC\) with \(BD\) works (they may cross, or one may go around the outside).
Degrees: \(P = 3\), \(Q = 2\), \(R = 3\), \(S = 2\), \(T = 2\). \(P\) and \(R\) are odd, so there is no Eulerian circuit: some streets must be driven twice.
Repeat the shortest route between the two odd vertices. That makes every degree even, so a circuit exists.
| \(P\text{–}Q\text{–}R\) | \(=\) | \(5 + 4 = 9\) |
| \(P\text{–}S\text{–}R\) | \(=\) | \(3 + 6 = 9\) |
| \(P\text{–}T\text{–}R\) | \(=\) | \(2 + 5 = 7\) |
| \(\text{all streets}\) | \(=\) | \(5 + 4 + 6 + 3 + 2 + 5 = 25\) |
| \(\text{total}\) | \(=\) | \(25 + 7 = \mathbf{32}\text{ km}\) |
One such route: \(Q\)–\(R\)–\(T\)–\(P\)–\(T\)–\(R\)–\(S\)–\(P\)–\(Q\), with \(PT\) and \(TR\) driven twice.
Degrees: \(A = 3\), \(B = 3\), \(C = 3\), \(D = 2\), \(E = 5\), \(F = 2\). The four odd vertices must be joined in two pairs by repeated roads. First find the shortest distance for each pair:
| \(AB = 6\) | \(AC = 11\) via \(B\) | \(AE = 5\) |
| \(BC = 5\) | \(BE = 3\) | \(CE = 8\) via \(B\) |
There are three ways to pair four vertices:
| \(AB + CE\) | \(=\) | \(6 + 8 = 14\) |
| \(AC + BE\) | \(=\) | \(11 + 3 = 14\) |
| \(AE + BC\) | \(=\) | \(5 + 5 = 10\) |
| \(\text{all roads}\) | \(=\) | \(49\) |
| \(\text{total}\) | \(=\) | \(49 + 10 = \mathbf{59}\text{ km}\) |
Repeat \(AE\) and \(BC\). The direct road \(CE\) (\(9\) km) is longer than \(C\)–\(B\)–\(E\) (\(8\) km), so always look for the shortest route, not just the direct road.
Common pitfalls
Frequently asked questions
What is the difference between an Eulerian trail and an Eulerian circuit?
Both use every edge exactly once. An Eulerian circuit finishes at the vertex where it started; an Eulerian trail that is not a circuit starts and finishes at two different vertices.
How do you know if a network has an Eulerian circuit?
The network must be connected and every vertex must have even degree. Then a circuit exists and it can start at any vertex.
Where does an Eulerian trail start and finish?
If a connected network has exactly two odd vertices, an Eulerian trail must start at one of them and finish at the other.
What is the Seven Bridges of Konigsberg problem?
The city of Konigsberg had seven bridges joining four land areas. People asked whether a walk could cross each bridge exactly once. Euler modelled it as a network and showed all four land areas had odd degree, so no such walk exists.
What is the fewest number of strokes needed to draw a figure?
Count the odd vertices. With none, one stroke is enough. Otherwise a connected figure needs half as many strokes as it has odd vertices, because each stroke can begin and end at only two of them.