Every edge exactly once
An Eulerian trail is a trail that uses every edge of a graph exactly once. If it also ends where it began, it is an Eulerian circuit. A snowplow that must clear every street, or a pen that must draw every line without being lifted, needs one.
Before trying any routes, count the degrees. In the figure-eight graph, two triangles ABC and CDE sharing C, the vertices A, B, D and E have degree 2 and C has degree 4.
The degrees: 2 at A, B, D and E, and 4 at C. All five are even.
An Eulerian circuit
Every degree is even, and a trail does use all six edges and return: A-B-C-D-E-C-A. It starts and ends at A and uses each edge once, so it is an Eulerian circuit.
The Eulerian circuit A-B-C-D-E-C-A, each edge numbered in the order it is used.
Why the degrees must be even
Follow a trail through a vertex in the middle of the route. It arrives along one edge and leaves along another, so each visit uses up two of that vertex’s edges, and a trail never uses an edge twice. If the trail covers every edge, the edges at each vertex it passes through are used up in pairs, so that vertex has even degree.
C has degree 4, and the circuit passes through it twice: it arrives along BC and leaves along CD, then arrives along EC and leaves along CA. In a circuit the start and the finish are the same vertex, so its first edge and its last edge make a pair as well. So every degree must be even.
The rule, and connectedness
The reverse holds too, provided the graph is connected: a connected graph has an Eulerian circuit exactly when every vertex has even degree.
Connectedness is part of the rule. Two separate triangles have every degree equal to 2, yet no route can reach both. Even degrees alone are not enough; the edges must all lie in one piece.
When every degree is even, a circuit can be built in pieces. Start anywhere and follow unused edges until you are stuck. With every degree even, you can only get stuck back at the start, because every other vertex you enter still has an unused edge to leave by. If edges are left over, start again from a vertex on the route that still has unused edges, make a second closed route, and splice it in at that vertex. On the figure-eight: from A, go A-B-C-A, which leaves CD, DE and EC unused. C is on that route, so go C-D-E-C, and splice it in at C to get A-B-C-D-E-C-A.
Exactly two odd vertices
Drop the edge EC. Now C has degree 3 and E has degree 1, and the other degrees are still even: exactly two vertices are odd. No circuit can cover every edge, since a circuit needs every degree even.
A trail can still cover every edge, if it starts at one odd vertex and finishes at the other. Those two are the only places with an edge that has no partner: the first edge leaves the start without arriving, and the last edge arrives at the finish without leaving. C-A-B-C-D-E uses all five edges, from C to E. It is an Eulerian trail.
So a connected graph has an Eulerian trail that is not a circuit exactly when it has exactly two vertices of odd degree, and the trail runs from one of them to the other. To see that one exists, join the two odd vertices with an extra edge: every degree becomes even, so there is an Eulerian circuit. Remove the extra edge from it, and what is left is a trail between the two odd vertices that uses every original edge.
With EC gone, C has degree 3 and E has degree 1: the only two odd vertices, in gold.
An Eulerian trail from C to E, each edge numbered in the order it is used.
Four odd vertices
In the town of Königsberg, seven bridges joined four land masses. As a graph, A meets 5 bridges and B, C and D meet 3 each, so all four vertices are odd. A trail has only two ends, and every vertex that is not an end needs even degree, so no route can cross every bridge exactly once.
The number of odd vertices is always even, by the handshake lemma, so the cases are 0, 2, 4 and so on. In a connected graph, 0 odd vertices give an Eulerian circuit, 2 give an Eulerian trail between them, and 4 or more give neither.
Königsberg: degrees 5, 3, 3 and 3. With four odd vertices, no trail crosses every bridge once.
odd vertices = 2, so an Euler trail exists, but it must run from one odd vertex to the other
Add edges until you can trace every edge once and finish where you started
A ring of 5 edges and one chord. The degrees are 3, 2, 3, 2 and 2, so exactly two vertices are odd, and the numbered gold trail runs from one of them to the other. Add a seventh edge and four vertices are odd, and no trail is drawn.
More than one trail
With more than two odd vertices, every edge can still be covered by several trails. Each odd vertex must be an end of some trail, and a trail has two ends, so a graph with 2k odd vertices needs at least k trails. For a connected graph, k are enough: join the odd vertices in pairs with k extra edges, take an Eulerian circuit, and remove the extra edges, which cuts the circuit into k trails. Königsberg, with 4 odd vertices, needs 2.
The usual mistakes
Miscounting the odd vertices. A degree is odd when it is 1, 3, 5 and so on; in the figure-eight with EC removed, they are C and E.
Counting the edges when the question asks about vertices.
Deciding that a graph with no Eulerian circuit has no Eulerian trail either. Two odd vertices rule out a circuit, but a trail runs between them.
Starting an Eulerian trail at an even vertex. When two vertices are odd, the trail must start at one of them and finish at the other.
Forgetting connectedness. Even degrees in two separate pieces allow no single route.
A snowplow and a pen plotter
In the first application below, a plow must drive every street of a village once, so the two junctions with an odd number of streets fix where it starts and finishes. In the second, a logo can be drawn in one stroke only when every point meets an even number of lines, and a logo with four odd points needs two strokes.
Worked example: A Snowplow That Must Clear Every Street of a Village Once, Where Its Route Starts and Finishes, and How Often It Crosses the Square
Question A village has a square S and six other junctions, A, B, C, D, E and F. Its ten streets join S to each of A, B, C, D, E and F, and also join A and B, B and C, C and D, and E and F. After a snowfall one plow clears the village, and one pass along a street clears its whole width. The driver wants a route that drives every street exactly once. (a) At which two junctions must the route start and finish? (b) How many times will the plow pass through the square, arriving along one street and leaving along another?
1.Model the village as a graph: a vertex for each junction and an edge for each street. A route that drives every street exactly once is an Eulerian trail, and the degrees decide whether one exists and where it can start and finish.
Each junction is a vertex and each street an edge. A route that drives every street once is an Eulerian trail. 2.Count the streets at each junction: S has 6, A, D, E and F have 2 each, and B and C have 3 each. Every time the plow passes through a junction it uses one street in and one street out, so a junction where the route neither starts nor finishes has an even degree.
The degrees: 6 at the square, 3 at B and at C, and 2 everywhere else. 3.(a) Only B and C have odd degree, and the graph is connected, so an Eulerian trail exists, and it must start at one of B and C and finish at the other. For example, B–A–S–B–C–S–E–F–S–D–C drives all 10 streets once each.
(a) B and C are the only odd vertices, so the route starts at one and finishes at the other. One such route is drawn. 4.The square is not an end of the route, so every pass through it uses 2 of its 6 streets, one to arrive and one to leave.
The square is not an end of the route, so every pass through it uses two of its streets. 5.(b) The plow passes through the square 6 ÷ 2 = 3 times. Check with the route in (a): it passes through S between A and B, between C and E, and between F and D.
(b) 6 ÷ 2 = 3 passes through the square.
Answer: (a) At B and C, the only 2 junctions with an odd number of streets: the route starts at one and finishes at the other; (b) 3 times
Common mistakes
- Starting at the square because it has the most streets. A junction where the route passes through uses its streets in pairs, so the route can only start and finish at the two junctions with an odd number of streets.
- Answering (b) with 6, the number of streets at the square. Each pass through the square uses two of its streets, one in and one out.
More eulerian and hamiltonian routes problems, worked step by step →
Worked example: A Pen Plotter Drawing Two Logos, Whether Each Can Be Drawn Without Lifting the Pen, and How Many Strokes It Needs
Question A pen plotter draws each logo as straight lines between labeled points, and it never draws a line twice. The first logo has seven points, A, B, C, D, E, G and X, and twelve lines: the square A–B, B–C, C–D and D–A, its two diagonals, which cross at X and are drawn as A–X, X–C, B–X and X–D, a triangle on the top side, D–E and E–C, and a triangle on the bottom side, A–G and G–B. The second logo is a window with nine points: the corners J, K, L and M, the middles of the sides N, P, Q and R, and the center S. Its twelve lines are J–N, N–K, K–P, P–L, L–Q, Q–M, M–R and R–J around the edge, and N–S, S–Q, P–S and S–R across the middle. (a) Can the plotter draw the first logo in one stroke, without lifting the pen, and if so, must the stroke end where it began? (b) What is the fewest number of strokes the plotter needs for the second logo?
1.Model each logo as a graph: a vertex for each labeled point and an edge for each line. One stroke that draws every line once is an Eulerian trail; if it ends where it began, it is an Eulerian circuit.
Each labeled point is a vertex and each line an edge. The diagonals cross at X. 2.First logo: count the lines at each point. A, B, C and D each meet 4 lines (two sides of the square, half a diagonal and a side of a triangle), X meets 4, and E and G meet 2 each.
Every point of the first logo meets an even number of lines. 3.(a) Every degree is even and the logo is connected, so it has an Eulerian circuit. Yes, it can be drawn in one stroke, and the stroke must end where it began, because a stroke that ended somewhere else would leave its two ends with an odd number of lines. One such stroke is A–B–C–D–A–X–C–E–D–X–B–G–A.
(a) Yes: an Eulerian circuit, so one stroke draws all 12 lines and ends where it began. 4.Second logo: the corners meet 2 lines each, the center S meets 4, and the middles N, P, Q and R meet 3 each. There are 4 points of odd degree.
The window has 4 points of odd degree: the middles of the sides. 5.A stroke passing through a point uses its lines in pairs, so each odd point must be an end of some stroke. A stroke has only two ends, so 4 odd points need at least 4 ÷ 2 = 2 strokes.
Four odd points need at least 4 ÷ 2 = 2 strokes. 6.(b) Two strokes are enough: N–S–Q–L–P–K–N–J–R–M–Q, which draws 10 lines, and then P–S–R, which draws the last 2. The fewest is 2 strokes.
(b) 2 strokes: the first draws 10 lines, the second the last 2.
Answer: (a) Yes: every point meets an even number of lines, 4 at A, B, C, D and X and 2 at E and G, so all 12 lines can be drawn in one stroke, and the stroke must end where it began; (b) 2 strokes, because the 4 middles of the sides each meet 3 lines
Common mistakes
- Answering (b) with 4 strokes, one for each point where three lines meet. Each stroke has two ends, so one stroke can start at one odd point and finish at another.
- Starting the first logo at A and expecting to finish at a different point. With every degree even, a stroke that uses every line returns to the point where it started.
More eulerian and hamiltonian routes problems, worked step by step →