Eulerian trails and circuits
An Eulerian trail uses every edge exactly once. In a connected graph, zero odd-degree vertices allow a circuit and a trail, exactly two allow a trail only, and more than two allow neither
\[\text{odd vertices}=0\;\Rightarrow\;\text{circuit and trail},\quad 2\;\Rightarrow\;\text{trail only},\quad >2\;\Rightarrow\;\text{neither}\]
- Check connectedness All edges must belong to one connected graph \(\displaystyle \text{connected}\;\text{is required}\)
- Count odd vertices Count vertices with odd degree before choosing a route class
- Use zero odd vertices A connected graph with all vertices even has both an Eulerian circuit and an Eulerian trail \(\displaystyle 0\text{ odd vertices}\;\Rightarrow\;\text{circuit and trail}\)
- Use two odd vertices With exactly two odd vertices, an Eulerian trail starts at one and finishes at the other \(\displaystyle B,E\text{ odd}\;\Rightarrow\;B\!\to\!E\text{ or }E\!\to\!B\)
Worked example
A connected graph has odd-degree vertices B and E. Decide whether it has an Eulerian trail, an Eulerian circuit or neither, and state the possible endpoints
\[\text{odd vertices: }B,E,\quad \text{number of odd vertices}=2\]
- \(\displaystyle \text{the graph is connected}\)The connectedness condition is satisfied
- \(\displaystyle \text{number of odd vertices}=2\)Only B and E have odd degree
- \(\displaystyle 2\text{ odd vertices}\;\Rightarrow\;\text{Eulerian trail only}\)Two odd vertices allow a trail but do not allow a circuit
- \(\displaystyle B\!\to\!E\text{ or }E\!\to\!B\)An Eulerian trail with two odd vertices must start and finish at the two odd vertices
Common mistakes
Misapplying the parity rule
✕\(\displaystyle 2\text{ odd vertices}\;\Rightarrow\;\text{Eulerian circuit}\)✓\(\displaystyle 2\text{ odd vertices}\;\Rightarrow\;\text{Eulerian trail only}\)
A connected graph with two odd vertices has an open Eulerian trail, whereas a circuit requires every vertex to be evenIgnoring connectedness
✕\(\displaystyle \text{edges in separate components and 0 odd}\;\Rightarrow\;\text{Eulerian circuit}\)✓\(\displaystyle \text{edges in separate components}\;\Rightarrow\;\text{neither}\)
Parity alone is not enough because one route cannot traverse edges in separate componentsStarting at an even vertex
✕\(\displaystyle A\text{ even},\;B,E\text{ odd}\;\Rightarrow\;A\text{ is a legal start}\)✓\(\displaystyle B,E\text{ odd}\;\Rightarrow\;B\text{ or }E\text{ must be the start}\)
For a two-odd-vertex Eulerian trail, the start and finish are the two odd verticesDifficulty levels
introContrast a connected all-even graph with a graph having too many odd vertices
standardUse the two-odd-vertex case to choose a trail and its possible endpoints
challengeIdentify a valid Eulerian route and reject routes with one named edge or start flaw
examChoose the Eulerian verdict justified by connectedness and vertex parity
Questions about this topic
What is the difference between an Eulerian trail and an Eulerian circuit?+
Both use every edge exactly once. A circuit starts and finishes at the same vertex, while a trail may have different endpoints
Why do two odd-degree vertices determine the endpoints?+
Each time a route enters an intermediate vertex it must also leave it, so only the start and finish can have an unmatched edge-end; those are the two odd vertices
Why is connectedness required?+
An Eulerian route is one sequence of adjacent edges. Separate components cannot all be traversed by one sequence
Can I use a calculator?+
No. This topic is practised without a calculator
Which year level and chapter is this?+
Year 12, VCE Units 3 & 4, General Mathematics, chapter 13: Graphs and networks
In this chapter
Count the vertices, edges and loops of a graphDegrees, the degree sum, and even and odd verticesGraph types, subgraphs, connection models and method selectionConnected graphs and bridgesIdentify isomorphic graphsPlanar graphs and drawings in planar formFaces and Euler's formulaRepresent a network in a matrixIdentify the network a connection matrix describesClassify a route: walk, trail, path, circuit or cycleEulerian trails and circuits: existence and identificationHamiltonian paths and cyclesRead a weighted graphThe shortest path by inspectionDijkstra's algorithm for shortest distances and routesTrees and spanning treesMinimum spanning trees by Prim's and Kruskal's algorithmsA full network investigation