All degrees even
Euler circuit exists
Connected graph.
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.
This page is easier if you are comfortable with:
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.
Euler walks exist when at most two vertices have odd degree.
Exactly two odd vertices means an Euler trail exists.
These examples are worked by hand, step by step, so you can compare your own working.
How many edges does an Euler circuit of traverse?
How many odd vertices does have?
How many odd vertices are there?
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
Euler circuit exists
Connected graph.
Euler trail (not circuit)
Start and end at odd vertices.
degrees 3, 3, 2, 2 sum to 10: 5 edges
Σ deg = 2E.
every degree 3: four odd vertices, no trail
More than two odd.
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.
Does a connected graph with four vertices of degree 2 have an Euler circuit?
Degrees 3, 3, 2, 2. How many edges? Is there a trail?
Does K₅ have an Euler circuit?
Does K₄ have an Euler trail?
edges odd ✗
vertices with odd degree ✓
Check degrees.
only degrees matter ✗
graph must be connected ✓
Isolated edges break it.
Σ deg = E ✗
Σ deg = 2E ✓
Each edge has two ends.
possible ✗
odd vertices come in pairs ✓
Σ deg is even.
Try each one on paper, then open the answer. Use the solver above to see the full working.
7
10
7
5
6
7
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
When the graph is connected and all degrees are even.
When exactly two vertices have odd degree.
The degrees sum to twice the edges.
Yes.
bipartite graphs.
Dirac’s theorem.
More in Discrete maths and number theory and the formula sheets.