How can we tell if a graph has an Euler path or circuit?

In solving the Königsberg bridge problem, Euler proved three theorems which answer this question.

EULER’S THEOREMS

Euler’s Theorem 1
If a graph has any vertices of odd degree, then it CANNOT have an EULER CIRCUIT.
AND
If a graph is connected and every vertex has even degree, then it has AT LEAST ONE EULER CIRCUIT (usually more).

Euler’s Theorem 2
If a graph has more than 2 vertices of odd degree, then it CANNOT have an EULER PATH.
AND
If a graph is connected and has exactly 2 vertices of odd degree, then it has AT LEAST ONE EULER PATH (usually more). Any such path must start at one of the odd-degree vertices and end at the other.

Euler’s Theorem 3
The sum of the degrees of all the vertices of a graph is an even number (exactly twice the number of edges).
In every graph, the number of vertices of odd degree must be even.

The implications of Euler's theorems are summarized in the table below:

# of ODD Vertices

Implication (for a connected graph)

0

There is at least
one Euler Circuit.

1

THIS IS IMPOSSIBLE!
(Try it yourself.)

2

There is no Euler Circuit but at least 1 Euler Path.

more than 2

There are no Euler Circuits
or Euler Paths.

Keep in mind:

  • An Euler Circuit IS a type of Euler Path but an Euler Path is not necessarily an Euler Circuit.
  • The sum of the degrees of all the vertices of a graph is twice the number of edges.
  • The number of vertices of odd degree must be even.

Back