Discrete mathematics
EULERIAN PATH
Definition
An Eulerian Path is a path in a graph that traverses every edge exactly
once. The path may start and end at different vertices.
The concept was introduced by Leonhard Euler while solving the famous
Seven Bridges of Königsberg problem.
Formal Definition
Let G=(V,E)G = (V, E)G=(V,E) be a graph where:
● VVV = set of vertices
● EEE = set of edges
A path in GGG is called an Eulerian Path if every edge in EEE is visited
exactly once.
Example
Consider the graph:
A ----- B
| |
| |
D ----- C
|
|
E
Degrees:
● deg(A) = 2
, ● deg(B) = 2
● deg(C) = 2
● deg(D) = 3
● deg(E) = 1
Eulerian Path:
E→D→A→B→C→D
Every edge is used exactly once.
Conditions for Eulerian Path
A connected graph contains an Eulerian Path if:
Condition 1
The graph must be connected.
Condition 2
The graph must have exactly 0 or 2 odd-degree vertices.
Cases
ber of Odd Vertices Result
an Circuit exists
an Path exists
than 2 ulerian Path
Eulerian Circuit
An Eulerian Circuit is a special Eulerian Path that starts and ends at the
same vertex.
EULERIAN PATH
Definition
An Eulerian Path is a path in a graph that traverses every edge exactly
once. The path may start and end at different vertices.
The concept was introduced by Leonhard Euler while solving the famous
Seven Bridges of Königsberg problem.
Formal Definition
Let G=(V,E)G = (V, E)G=(V,E) be a graph where:
● VVV = set of vertices
● EEE = set of edges
A path in GGG is called an Eulerian Path if every edge in EEE is visited
exactly once.
Example
Consider the graph:
A ----- B
| |
| |
D ----- C
|
|
E
Degrees:
● deg(A) = 2
, ● deg(B) = 2
● deg(C) = 2
● deg(D) = 3
● deg(E) = 1
Eulerian Path:
E→D→A→B→C→D
Every edge is used exactly once.
Conditions for Eulerian Path
A connected graph contains an Eulerian Path if:
Condition 1
The graph must be connected.
Condition 2
The graph must have exactly 0 or 2 odd-degree vertices.
Cases
ber of Odd Vertices Result
an Circuit exists
an Path exists
than 2 ulerian Path
Eulerian Circuit
An Eulerian Circuit is a special Eulerian Path that starts and ends at the
same vertex.
