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

# Euler and Hamilton circuits with conditions

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2073 Magh, 2+2+2+2 marks
- Video: [Euler and Hamiltonian paths and circuits](https://www.youtube.com/watch?v=2bD80pSg_mg) — CBlissMath
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/euler-and-hamilton-circuits-conditions
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Explain the Euler circuit and Hamilton circuit with example. State the necessary and the sufficient conditions for them.

## Short answer

An Euler circuit traverses every edge exactly once; exists iff all vertices have even degree. A Hamilton circuit visits every vertex exactly once and returns to start; no simple necessary and sufficient condition exists, but Dirac's theorem (n≥3, all degrees ≥ n/2) is sufficient. Example: bowtie has Euler circuit, pentagon has Hamilton circuit.

## Answer

#### Euler circuit
A closed walk that uses every **edge** exactly once. Example: the bowtie with edges ab, bc, ca, cd, de, ec has the Euler circuit c → a → b → c → d → e → c.

```text
   a         d
   |\       /|
   | \     / |
   |  \   /  |
   |   \ /   |
   |    c    |
   |   / \   |
   |  /   \  |
   | /     \ |
   b         e     (edges: ab, ac, bc, cd, ce, de)
```
(Bowtie: triangles abc and cde sharing vertex c.)

**Conditions:** a connected graph has an Euler circuit if and only if every vertex has even degree. It has an Euler path (not a circuit) if and only if exactly two vertices have odd degree.

#### Hamilton circuit
A cycle that visits every **vertex** exactly once and returns to the start. Example: in the pentagon a–b–c–d–e–a, the circuit a, b, c, d, e, a visits all five vertices.

```text
      a
     / \
    e   b
    |   |
    d---c
```

**Conditions:** there is no known simple necessary and sufficient condition.
- Necessary: the graph is connected, every vertex has degree ≥ 2, and it has no cut vertex.
- Sufficient (Dirac): a simple graph with n ≥ 3 vertices in which every vertex has degree ≥ n/2 has a Hamilton circuit.
- Sufficient (Ore): if a simple graph with n ≥ 3 vertices has deg(u) + deg(v) ≥ n for every pair of non-adjacent vertices, it is Hamiltonian.

| Point | Euler circuit | Hamilton circuit |
|---|---|---|
| Visits | all edges once | all vertices once |
| Test | all degrees even (exact) | only sufficient conditions known |
| Example with only this | bowtie (not Hamiltonian) | K₄ (degrees 3, not Eulerian) |

## Check yourself

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

1. Euler circuit exists in a connected graph iff:
   A. Every vertex has degree >= 2
   B. The graph is complete
   C. Exactly two vertices have odd degree
   D. Every vertex has even degree
   Answer: D. This is exact. (Key point: Euler condition)

2. For Hamilton circuits:
   A. No simple necessary and sufficient condition is known
   B. Even degrees are necessary and sufficient
   C. Degree >= 2 is necessary and sufficient
   D. Connectedness is sufficient
   Answer: A. Only necessary or sufficient conditions are known. (Key point: Hamilton test)

3. Dirac's theorem guarantees a Hamilton circuit if:
   A. every degree is even
   B. n >= 3 and every degree >= n/2
   C. n >= 3 and every degree >= 2
   D. the graph is connected
   Answer: B. It is a sufficient condition. (Key point: Dirac)

4. Ore's condition requires:
   A. deg(u) + deg(v) <= n
   B. deg(u) = deg(v)
   C. deg(u) + deg(v) >= n for every non-adjacent pair
   D. deg(u) >= n for all u
   Answer: C. Ore generalises Dirac. (Key point: Ore)

## Related in Discrete Structure

- [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×
- [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×
- [Euler versus Hamilton circuit](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aeuler-vs-hamilton-difference) — Discrete Structure, chapter 4, asked 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