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

# Conditions for Euler circuits and paths

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2071 Bhadra, 2 marks
- Video: [Graph Theory:  Euler Paths and Euler Circuits](https://www.youtube.com/watch?v=5M-m62qTR-s) — Mathispower4u
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/euler-circuit-path-conditions
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

State the necessary and sufficient conditions for Euler circuits and paths.

## Short answer

For a connected undirected graph, an Euler circuit exists iff every vertex has even degree. An Euler path exists iff exactly two vertices have odd degree. For directed graphs, circuit requires in-degree equals out-degree for all vertices; a path requires one vertex with out = in + 1, one with in = out + 1, others equal.

## Answer

For a **connected undirected graph**:

- **Euler circuit** (closed walk through every edge exactly once): exists **if and only if every vertex has even degree**.
- **Euler path** (open walk through every edge exactly once): exists **if and only if exactly two vertices have odd degree**; the path starts at one of them and ends at the other.

Necessity: every time a walk passes through a vertex it uses two edges (one in, one out), so the edges at each vertex pair up. Only the starting and ending vertex of an open path can be left with an unpaired edge, so they alone may have odd degree. Since the number of odd-degree vertices in any graph is even, the possible counts are 0 (circuit) or 2 (path). Sufficiency is shown by building a circuit, or path, and splicing in closed trails over any unused edges.

For a **directed graph**: an Euler circuit exists iff the graph is connected and in-degree = out-degree for every vertex. An Euler path exists iff all vertices have in = out except one with out = in + 1 (start) and one with in = out + 1 (end).

Example: K₅ (all degrees 4) has an Euler circuit; K₄ (all degrees 3, four odd vertices) has neither.

## Check yourself

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

1. Euler circuit in a connected undirected graph exists iff:
   A. Exactly two vertices are odd
   B. Some vertex has even degree
   C. Every vertex has even degree
   D. All vertices have odd degree
   Answer: C. Edges pair up at every vertex. (Key point: Circuit)

2. Euler path (open) exists iff:
   A. Exactly one
   B. Four
   C. None
   D. Exactly two vertices have odd degree
   Answer: D. It runs between the two odd vertices. (Key point: Path)

3. Why does K4 have neither?
   A. All four vertices have odd degree 3
   B. It is disconnected
   C. All degrees are even
   D. Only two vertices are odd
   Answer: A. Four odd vertices exceeds the limit of two. (Key point: K4)

## Close variants set in other exams

- [Euler path and circuit with conditions](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aexplain-euler-path-circuit-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

## Related in other subjects

- [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
- [Necessary conditions; deadlock prevention](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-prevention-necessary-conditions) — Operating System, chapter 7
- [Importance of initial conditions and equivalent circuits](https://www.bctengineer.com/question.md?key=semester_3%2Felectrical_circuit_theory%3Aimportance-of-initial-conditions-equivalent-circuits) — Electrical Circuit Theory, chapter 2