---
title: "Euler path and circuit with conditions"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:explain-euler-path-circuit-conditions"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/explain-euler-path-circuit-conditions
site: BCT Engineering
---

# Euler path and circuit with conditions

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2072 Asoj, 5+3 marks
- Video: [Euler Graph in Graph Theory | Euler Path & Euler Circuit with examples](https://www.youtube.com/watch?v=FoiLXsV-bnI) — Gate Smashers
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/explain-euler-path-circuit-conditions
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Explain the Euler path and Euler circuit with the help of a diagram. State the necessary and the sufficient conditions for Euler circuits and paths.

## Short answer

An Euler circuit uses every edge exactly once and returns to start; exists iff all vertices have even degree. An Euler path uses every edge exactly once but starts and ends at different vertices; exists iff exactly two vertices have odd degree. Both require a connected graph.

## Answer

#### Definitions
- **Euler circuit:** a closed walk that uses every edge of the graph exactly once, starting and ending at the same vertex.
- **Euler path:** a walk that uses every edge exactly once but starts and ends at different vertices.

#### Diagrams
Euler circuit (every vertex even):

```text
   a         d
   |\       /|
   | \     / |       edges: ab, ac, bc, cd, ce, de
   |  \   /  |       degrees: c = 4, others 2
   |   \ /   |       circuit: c, a, b, c, d, e, c
   |    c    |
   |   / \   |
   |  /   \  |
   | /     \ |
   b         e
```

Euler path (two odd vertices):

```text
 a ------- b
 | \       |        edges: ab, bc, cd, da, ac
 |   \     |        odd vertices: a, c (degree 3)
 |     \   |        path: a, b, c, d, a, c
 d ------- c
```

#### Necessary and sufficient conditions (connected undirected graph)
1. **Euler circuit:** exists if and only if every vertex has even degree.
2. **Euler path (not circuit):** exists if and only if exactly two vertices have odd degree. It must start at one odd vertex and end at the other.

Why necessary: each time the walk passes through a vertex it uses one edge to enter and one to leave, so the edges at each vertex pair up. Only the start and end of an open path can have odd degree. Why sufficient: when all degrees are even, a trail can only get stuck at its starting vertex, so it closes into a circuit; any unused edges form further closed trails, which can be spliced in to give one Euler circuit.

For **directed** graphs (connected): a circuit exists iff in-degree = out-degree at every vertex; a path exists iff one vertex has out − in = 1, one has in − out = 1, and all others are balanced.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. An Euler circuit exists in a connected graph iff:
   A. Exactly two vertices have odd degree
   B. All vertices have odd degree
   C. The graph is a cycle
   D. All vertices have even degree
   Answer: D. This is Euler's theorem. (Key point: Circuit)

2. An Euler path that is not a circuit exists iff:
   A. Exactly two vertices have odd degree
   B. Exactly one vertex has odd degree
   C. All degrees are even
   D. Three vertices have odd degree
   Answer: A. It starts at one odd vertex and ends at the other. (Key point: Path)

3. Why must degrees be even for a circuit?
   A. Edges are directed
   B. Each pass through a vertex uses one edge in and one out, pairing edges
   C. Every vertex is a leaf
   D. The graph is complete
   Answer: B. Only the start and end of an open path can have an unpaired edge. (Key point: Necessity)

4. A directed Euler path exists iff:
   A. All in = out
   B. Two vertices have in = 0
   C. One vertex has out - in = 1, one has in - out = 1, others balanced
   D. All out = 0
   Answer: C. Start and end vertices are the only unbalanced ones. (Key point: Directed path)

## Close variants set in other exams

- [Conditions for Euler circuits and paths](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aeuler-circuit-path-conditions) — Discrete Structure, chapter 4, asked 2×

## Related in Discrete Structure

- [Euler and Hamilton circuits with conditions](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aeuler-and-hamilton-circuits-conditions) — Discrete Structure, chapter 4
- [Hamiltonian path and circuit with diagram](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahamiltonian-path-circuit-diagram) — Discrete Structure, chapter 4

## Related in other subjects

- [Reactance diagram: 100 MVA base, two parallel paths](https://www.bctengineer.com/question.md?key=semester_4%2Fpower_system_analysis_i%3Areactance-diagram-90mva-two-paths) — Power System Analysis I, chapter 3
- [Return current path in high-speed circuits](https://www.bctengineer.com/question.md?key=semester_5%2Finstrumentation_ii%3Ahigh-speed-ground-return) — Instrumentation II, chapter 6
- [Deadlock; necessary conditions with examples](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-necessary-conditions-examples) — Operating System, chapter 7
- [Deadlock conditions and why all necessary](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-conditions-why-necessary) — Operating System, chapter 7