| 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 |