---
title: "Euler versus Hamilton circuit"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:euler-vs-hamilton-difference"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/euler-vs-hamilton-difference
site: BCT Engineering
---

# Euler versus Hamilton circuit

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2075 Bhadra, 3 marks; 2074 Bhadra, 4 marks; 2071 Bhadra, 2 marks; 2070 Magh, 3 marks (asked 4 times)
- Video: [Euler and Hamiltonian Paths and Circuits](https://www.youtube.com/watch?v=AwsMTEl79wI) — James Olsen
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/euler-vs-hamilton-difference
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

How does an Euler circuit (graph) differ from a Hamiltonian circuit (graph)? Explain.

## Short answer

An Euler circuit traverses every edge exactly once and exists when the graph is connected and all vertices have even degree. A Hamiltonian circuit visits every vertex exactly once, but no simple necessary and sufficient condition exists; the problem is NP-complete, though sufficient conditions like Dirac's theorem (n≥3, min degree ≥ n/2) apply.

## Answer

An **Euler circuit** is a closed walk that uses every **edge** exactly once. A **Hamiltonian circuit** is a cycle that visits every **vertex** exactly once (and returns to the start).

| Point | Euler circuit | Hamiltonian circuit |
|---|---|---|
| Visits | every edge exactly once | every vertex exactly once |
| Vertices | may be repeated | no repetition (except start = end) |
| Edges | none repeated | some edges may be unused |
| Existence test | simple: connected and every degree even | no simple necessary and sufficient test (NP-complete) |
| Known conditions | exact (Euler's theorem) | only sufficient: Dirac (n ≥ 3, deg(v) ≥ n/2), Ore |
| Example | bowtie (two triangles sharing a vertex) has one, but no Hamiltonian circuit | K₄ has one, but no Euler circuit (all degrees 3) |

Bowtie: edges a–b, b–c, c–a, c–d, d–e, e–c. Euler circuit: c, a, b, c, d, e, c. No Hamiltonian circuit, since c would have to be visited twice.

Some graphs have both, for example the cycle C₅ or K₅.

## Check yourself

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

1. What does an Euler circuit use exactly once, compared with a Hamiltonian circuit?
   A. Euler: every edge; Hamiltonian: every vertex
   B. Euler: every vertex; Hamiltonian: every edge
   C. Both: every edge
   D. Both: every vertex
   Answer: A. An Euler circuit covers every edge once, while a Hamiltonian circuit visits every vertex once. (Key point: Euler vs Hamilton)

2. Which statement about testing existence is correct?
   A. Both have exact degree tests
   B. Euler has an exact degree test; Hamiltonian has no simple necessary and sufficient test
   C. Hamiltonian has an exact degree test; Euler has none
   D. Neither can be tested at all
   Answer: B. Euler's theorem (connected, all degrees even) is exact; for Hamiltonian circuits only sufficient conditions like Dirac and Ore are known. (Key point: Existence test)

3. Dirac's condition (n >= 3, deg(v) >= n/2) for a Hamiltonian circuit is:
   A. Necessary and sufficient
   B. Only necessary
   C. Only sufficient, not necessary
   D. Needed for Euler circuits
   Answer: C. Graphs can be Hamiltonian without satisfying Dirac, so it only guarantees a circuit. (Key point: Dirac condition)

4. Why does the bowtie (two triangles sharing vertex c) have no Hamiltonian circuit?
   A. It has an odd number of edges
   B. Some vertex has odd degree
   C. It is not connected
   D. Vertex c would have to be visited twice
   Answer: D. Any cycle through all five vertices must pass through c twice, but a Hamiltonian circuit visits each vertex once. It does have an Euler circuit since all degrees are even. (Key point: Bowtie example)

## Related in Discrete Structure

- [Short note: Hamiltonian graph](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Ahamiltonian-graph-short-note) — Discrete Structure, chapter 4
- [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
- [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 other subjects

- [Flood frequency graph, 30-year flood, 1981-2000](https://www.bctengineer.com/question.md?key=semester_5%2Fengineering_hydrology%3Areturn-period-graph-30yr-1981-2000) — Engineering Hydrology, chapter 6
- [Series versus parallel circuit comparison](https://www.bctengineer.com/question.md?key=semester_1%2Fbasic_electrical_engineering%3Aseries-parallel-comparison-table) — Basic Electrical Engineering, chapter 1
- [Vacuum versus SF6 circuit breaker](https://www.bctengineer.com/question.md?key=semester_8%2Fpower_plant_design%3Avcb-vs-sf6) — Power Plant Design, chapter 4