Below is a simple, clear, and exam-oriented explanation of Eulerian Chains (Trails) and Eulerian Cycles (Circuits) — perfect for BCA/MCA/Engineering/Discrete Mathematics exams.
⭐ Eulerian Chains and Cycles
Eulerian paths and cycles are named after Leonhard Euler, who solved the famous Seven Bridges of Königsberg problem using these concepts.
They deal with walking through all edges of a graph exactly once.
⭐ 1. Basic Terminology
Before defining Euler paths, understand:
✔ Trail
A walk that does not repeat edges.
✔ Path
A walk that does not repeat vertices.
✔ Circuit / Cycle
Begins and ends at the same vertex.
⭐ 2. Eulerian Trail (Eulerian Chain)
An Eulerian trail (also called Eulerian chain) is:
A trail that uses every edge exactly once, but does not need to return to the starting vertex.
Example:
Start at one vertex → use every edge → end at a different vertex.
⭐ 3. Eulerian Circuit (Eulerian Cycle)
An Eulerian circuit (or Eulerian cycle) is:
A cycle that uses every edge exactly once, and starts and ends at the same vertex.
⭐ 4. Conditions for Eulerian Trails and Eulerian Circuits
The conditions depend on the degree of vertices in an undirected graph.
⭐ ⭐ A. Conditions for Eulerian Circuit
A connected undirected graph has an Eulerian circuit if and only if:
✔ All vertices have even degree
That is:
[
\deg(v) \equiv 0 \pmod{2} \quad \forall v \in V
]
✔ Graph must be connected
(except isolated vertices)
⭐ ⭐ B. Conditions for Eulerian Trail
A connected undirected graph has an Eulerian trail (but NOT a circuit) if and only if:
✔ Exactly 0 or 2 vertices have odd degree
Cases:
- 0 odd-degree vertices → Eulerian circuit
- 2 odd-degree vertices → Eulerian trail
If 2 odd-degree vertices, trail starts at one and ends at the other.
⭐ ⭐ C. No Eulerian Trail or Circuit
If a graph has more than 2 vertices with odd degree →
It is not Eulerian.
⭐ 5. Examples
✔ Example 1: All even degrees → Eulerian circuit
Graph with degrees:
2, 2, 2, 2
→ Eulerian circuit exists.
✔ Example 2: Two odd-degree vertices → Eulerian trail
Degrees:
3, 3, 2, 2
→ Eulerian trail exists, but not circuit.
✔ Example 3: More than two odd vertices
Degrees:
3, 3, 3, 1
→ No Eulerian trail or circuit.
⭐ 6. Eulerian Graph
A graph containing an Eulerian circuit is called an Eulerian graph.
⭐ 7. Directed Graph Case (Digraphs)
✔ Eulerian Circuit
A directed graph has an Eulerian circuit if:
- Every vertex has in-degree = out-degree
- Graph is strongly connected
✔ Eulerian Trail
A directed graph has an Eulerian trail if:
- Exactly one vertex has:
[
out\deg(v) = in\deg(v) + 1
] - Exactly one vertex has:
[
in\deg(w) = out\deg(w) + 1
] - All others satisfy:
[
in\deg = out\deg
] - Graph is connected in underlying sense.
⭐ 8. Famous Example: Seven Bridges of Königsberg
Euler proved it was impossible to cross each bridge once because:
- The graph had 4 vertices with odd degree
So no Eulerian trail exists.
⭐ 9. Algorithms for Finding Euler Paths
1️⃣ Fleury’s Algorithm
- Easy, intuitive
- Avoids using bridges unless necessary
2️⃣ Hierholzer’s Algorithm
- Efficient
- Used in computer science and programming
⭐ 10. Applications of Eulerian Graphs
✔ Network routing
✔ GPS navigation
✔ Postman problem
✔ DNA sequencing
✔ PCB design (circuit tracing)
✔ Maze solving
✔ Transportation & logistics
✔ Robotics path planning
⭐ Quick Exam-Oriented Summary
Eulerian Trail:
A trail that uses every edge exactly once.
Eulerian Circuit:
A cycle that uses every edge exactly once and returns to start.
Conditions (Undirected Graph):
- Eulerian circuit: All vertices even degree
- Eulerian trail: Exactly 0 or 2 vertices odd degree
- No Eulerian trail: >2 odd-degree vertices
Directed Graph:
- Circuit: in-degree = out-degree
- Trail: one vertex has +1 out-degree, one has +1 in-degree