---
title: "Short note: Hamiltonian graph"
subject: "Discrete Structure"
chapter: 4
key: "semester_4/discrete_structure:hamiltonian-graph-short-note"
source: https://www.bctengineer.com/q/semester_4/discrete_structure/hamiltonian-graph-short-note
site: BCT Engineering
---

# Short note: Hamiltonian graph

Discrete Structure · Chapter 4: Graph Theory

- Asked in: 2068 Bhadra, 3 marks
- Video: [Hamiltonian Graph || Hamiltonian Circuit || Hamiltonian Path || Discrete Mathematics || DMS || GATE](https://www.youtube.com/watch?v=mNYvM782WUc) — Sudhakar Atchala
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/discrete_structure/hamiltonian-graph-short-note
- Whole chapter: https://www.bctengineer.com/md/semester_4/discrete_structure/chapter-4

## Question

Write a short note on Hamiltonian graph.

## Short answer

A Hamiltonian graph contains a cycle visiting every vertex exactly once. No simple necessary and sufficient condition is known; sufficient conditions include Dirac's theorem (minimum degree ≥ n/2) and Ore's theorem (for non-adjacent pairs, degree sum ≥ n). It differs from Eulerian graphs by focusing on vertices rather than edges.

## Answer

A **Hamiltonian circuit** in a graph is a simple cycle that passes through every vertex exactly once; a graph containing one is a **Hamiltonian graph**. A **Hamiltonian path** visits every vertex once but need not return to the start. The name comes from Sir W. R. Hamilton's "Icosian game" (a tour of the dodecahedron's vertices).

**Examples:** every cycle Cₙ, the complete graph Kₙ (n ≥ 3) and the cube Q₃ are Hamiltonian. K₂,₃ and the Petersen graph are not.

```text
      a
     / \
    e   b      Hamiltonian circuit: a, b, c, d, e, a
    |   |
    d---c
```

**Conditions:** no simple necessary and sufficient condition is known (deciding whether a graph is Hamiltonian is an NP-complete problem).
- Necessary: connected, no cut vertex, every vertex has degree ≥ 2.
- **Dirac's theorem:** a simple graph with n ≥ 3 vertices and every degree ≥ n/2 is Hamiltonian.
- **Ore's theorem:** if a simple graph with n ≥ 3 vertices has deg(u) + deg(v) ≥ n for every pair of non-adjacent vertices, it is Hamiltonian.

**Difference from Euler:** Hamilton concerns vertices; Euler concerns edges.

Application: the travelling salesman problem asks for the cheapest Hamiltonian circuit in a weighted complete graph.

## Check yourself

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

1. A Hamiltonian circuit is a cycle that:
   A. Uses every edge once
   B. Passes through every vertex exactly once
   C. Visits some vertices twice
   D. Has no repeated edges but skips vertices
   Answer: B. A graph containing one is Hamiltonian. (Key point: Definition)

2. Dirac's theorem states a simple graph with n >= 3 is Hamiltonian if:
   A. every degree is even
   B. degree sum is even
   C. every degree >= n/2
   D. it has no cut vertex
   Answer: C. It is a sufficient condition only. (Key point: Dirac)

3. The travelling salesman problem asks for:
   A. The shortest Euler circuit
   B. The minimum spanning tree
   C. The chromatic number
   D. The cheapest Hamiltonian circuit in a weighted complete graph
   Answer: D. It is an application of Hamiltonian circuits. (Key point: TSP)

## Related in Discrete Structure

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