Euler Circuit and Trail Explained with Worked Examples

A connected graph has an Euler circuit (a closed walk using every edge exactly once) if and only if every vertex has even degree. It has an Euler trail (an open walk using every edge once) if and only if exactly two vertices have odd degree.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Euler circuit and trail means

The complete graph has every degree equal to 4, so it has an Euler circuit that uses all edges (edges in a complete graph). has four vertices of degree 3: four odd vertices, so neither a circuit nor a trail exists. A graph with degrees 2, 3, 3, 2 has exactly two odd vertices, so it has an Euler trail starting at one odd vertex and ending at the other. The Königsberg bridges graph has four odd vertices: no Euler walk.

The condition follows from counting: each time a walk passes through a vertex it uses two edges, so interior vertices need even degree; only the start and end of a trail can be odd. The number of odd vertices is always even, by the handshaking lemma (the handshaking lemma), so 0, 2, 4, … are the only possibilities.

The route inspection (Chinese postman) problem finds the cheapest closed walk covering every edge by duplicating edges to make all degrees even (route inspection). Euler circuits are easy to detect, unlike Hamilton cycles (Dirac's theorem), and the graph's connectivity is related to bipartite graphs and walks.

What is it used for?

Euler walks exist when at most two vertices have odd degree.

How to use euler circuit and trail

  1. Check that the graph is connected.
  2. Compute the degree of each vertex.
  3. Count the odd vertices: 0 gives a circuit, 2 gives a trail, otherwise neither.
  4. To find the walk, use Hierholzer's algorithm.

Graph

Degrees of a graph with two odd vertices: 2, 3, 3, 2oddodd00.511.522.533.544.5500.511.522.533.54Degrees of a graph with two odd vertices: 2, 3, 3, 2vertexyGraph with x from 0 to 5 and y from 0 to 4. Shows bars (4); point odd at (2, 3); point odd at (3, 3).

Exactly two odd vertices means an Euler trail exists.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: K₅

How many edges does an Euler circuit of traverse?

Worked example
Answer
1010
  1. Degrees
  2. Edges

Example 2: K₄

How many odd vertices does have?

Worked example
Answer
4 (no Euler walk)4\ (\text{no Euler walk})
  1. Degrees

Example 3: degrees 2, 3, 3, 2

How many odd vertices are there?

Worked example
Answer
2 (Euler trail)2\ (\text{Euler trail})
  1. Odd degrees

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

All degrees even

Euler circuit exists

Connected graph.

Exactly two odd

Euler trail (not circuit)

Start and end at odd vertices.

Handshaking

degrees 3, 3, 2, 2 sum to 10: 5 edges

Σ deg = 2E.

K₄

every degree 3: four odd vertices, no trail

More than two odd.

Word problems

A connected graph has an Euler circuit iff every vertex has even degree, and an Euler trail iff exactly two vertices have odd degree. Always Σ deg(v) = 2E.

Degrees 2, 2, 2, 2

Does a connected graph with four vertices of degree 2 have an Euler circuit?

  1. All even
  2. Check: sum 8, 4 edges (a 4-cycle) ✓Yes.

Handshaking

Degrees 3, 3, 2, 2. How many edges? Is there a trail?

  1. Sum 10, edges 5
  2. Two odd vertices
  3. Check: ✓5 edges; an Euler trail.

K₅ Higher

Does K₅ have an Euler circuit?

  1. Each degree 4
  2. Check: all even, 10 edges ✓Yes.

K₄ Higher

Does K₄ have an Euler trail?

  1. Each degree 3, four odd vertices
  2. Check: more than two odd ✓No.

Common mistakes

Counting odd edges

edges odd ✗

vertices with odd degree ✓

Check degrees.

Forgetting connectivity

only degrees matter ✗

graph must be connected ✓

Isolated edges break it.

Sum of degrees = E

Σ deg = E ✗

Σ deg = 2E ✓

Each edge has two ends.

One odd vertex

possible ✗

odd vertices come in pairs ✓

Σ deg is even.

Exam tips

  1. All even: circuit.
  2. Two odd: trail.
  3. Σ deg = 2E.
  4. Connected.
  5. Odd vertices are even in number.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Edges when degrees sum to 14 Foundation

7

2. Edges in K₅ Foundation

10

3. Edges when degrees are 4, 4, 2, 2, 2 Foundation

7

4. Degree of each vertex in K₆ Higher

5

5. Does K₆ have an Euler circuit (degree 5 odd)? odd count Higher

6

6. Edges in a 7-cycle Higher

7

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Euler circuit
Closed walk using each edge once.
Euler trail
Open walk using each edge once.
Degree
Number of edges at a vertex.
Handshaking lemma
Σ deg = 2E.
Connected graph
One component.
Eulerian graph
Has an Euler circuit.

Frequently asked questions

When does an Euler circuit exist?

When the graph is connected and all degrees are even.

When does an Euler trail exist?

When exactly two vertices have odd degree.

What is the handshaking lemma?

The degrees sum to twice the edges.

Does K₅ have an Euler circuit?

Yes.

Which page covers bipartite graphs?

bipartite graphs.

Which page covers Dirac’s theorem?

Dirac’s theorem.

More in Discrete maths and number theory and the formula sheets.