---
title: "Hamiltonian path and circuit with diagram"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:hamiltonian-path-circuit-diagram"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/hamiltonian-path-circuit-diagram
site: BCT Engineering
---

# Hamiltonian path and circuit with diagram

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2071 Bhadra, 3 marks
- Video: [Hamiltonian Graph with examples | Hamiltonian Path & Circuit](https://www.youtube.com/watch?v=GiClUAJMMtw) — 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/hamiltonian-path-circuit-diagram
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Explain the Hamiltonian path and Hamiltonian circuit with the help of a diagram.

## Short answer

A Hamiltonian path visits every vertex exactly once; a Hamiltonian circuit is a Hamiltonian path that returns to the start. A graph with a Hamiltonian circuit is Hamiltonian. No simple exact test exists; necessary conditions include connectivity and minimum degree ≥2. Dirac's condition (n≥3, deg(v) ≥ n/2) is sufficient.

## Answer

A **Hamiltonian path** is a simple path that passes through every vertex of the graph exactly once. A **Hamiltonian circuit** (cycle) is a simple cycle that passes through every vertex exactly once and ends where it started. A graph with a Hamiltonian circuit is called a Hamiltonian graph. Unlike in Euler paths, some edges may be left unused.

#### Diagram 1: a Hamiltonian circuit (and so also a path)
```text
        a
       / \
      e   b           edges: ab, bc, cd, de, ea, plus chord ec
      |\  |
      | \ |           circuit: a, b, c, d, e, a
      d---c
```
The circuit a → b → c → d → e → a visits all 5 vertices once; the chord ec is not used.

#### Diagram 2: a Hamiltonian path but no circuit
```text
   a ---- b ---- c
          |      |       edges: ab, bc, bd, cd
          d ------+
```
The path a → b → c → d (or a → b → d → c) visits every vertex once, so a Hamiltonian path exists. There is no Hamiltonian circuit because vertex a has degree 1, and a cycle needs degree at least 2 at every vertex.

No simple exact test is known. A Hamiltonian circuit needs a connected graph with no cut vertex and all degrees ≥ 2; Dirac's condition (n ≥ 3, deg(v) ≥ n/2 for all v) is sufficient.

## Check yourself

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

1. A Hamiltonian path differs from a Hamiltonian circuit in that:
   A. It uses every edge once
   B. It may repeat vertices
   C. It must be closed
   D. It visits every vertex once but need not return to the start
   Answer: D. A circuit is a closed cycle through every vertex. (Key point: Path vs circuit)

2. Compared with Euler paths, a Hamiltonian circuit:
   A. May leave edges unused
   B. Must use all edges
   C. Must repeat edges
   D. Only exists for even degrees
   Answer: A. It cares about vertices, not edges. (Key point: Unused edges)

3. Why does the graph with edges ab, bc, bd, cd have no Hamiltonian circuit?
   A. It has too many edges
   B. Vertex a has degree 1
   C. It is disconnected
   D. All vertices have degree 3
   Answer: B. A cycle needs degree >= 2 at every vertex. (Key point: No circuit)

## Related in Discrete Structure

- [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

- [Block diagram of a two-stage RC circuit](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Abd-rc-two-stage) — Control Systems, chapter 2
- [Block diagram model of R-L-C-L-R circuit](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Abd-r1l1-c-l2r2) — Control Systems, chapter 2
- [Series path with parallel capacitor](https://www.bctengineer.com/question.md?key=semester_1%2Fbasic_electrical_engineering%3Aseries-rl-parallel-capacitor-240v) — Basic Electrical Engineering, chapter 6
- [Two-ray model advantages and path loss derivation](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Atwo-ray-advantages-path-loss) — Wireless Communication, chapter 3