PGDDSA Study · Semester 1

PGD01C01

Module 2 · Graph Theory

Paths, Circuits, Eulerian and Hamiltonian Circuits

Core Titles

Key headlines and terms for quick recall

Walk, Trail, Path, Circuit, Cycle
Eulerian trail / circuit — uses every edge once
Hamiltonian path / circuit — visits every vertex once
Euler's theorem for Eulerian graphs
Connected graph
Sufficient conditions for Hamiltonian (Dirac, Ore)

Basic Idea

What it is, why it matters, how it works

Walk → Trail → Path

Walk — alternating sequence of vertices and edges. Repetition allowed.
Trail — walk with no repeated edges.
Path — walk with no repeated vertices (hence no repeated edges either).
Circuit — a closed trail (start = end).
Cycle — a closed path (closed walk with no repeated vertex except start/end).

Eulerian (edges)

An Eulerian trail uses every edge exactly once. If it's also closed, it's an Eulerian circuit.

Euler's theorem. A connected graph has:

An Eulerian circuit iff every vertex has even degree.
An Eulerian trail (open) iff exactly two vertices have odd degree (start and end).

Hamiltonian (vertices)

A Hamiltonian path visits every vertex exactly once. Hamiltonian circuit returns to the start.

There is no simple necessary-and-sufficient condition. Two well-known sufficient ones:

Dirac's theorem: simple graph on $n \ge 3$ vertices, each vertex with $\deg \ge n/2$ ⇒ Hamiltonian.
Ore's theorem: for every non-adjacent pair $u, v$ : $\deg(u) + \deg(v) \ge n$ ⇒ Hamiltonian.

Deciding Hamiltonicity in general is NP-complete — unlike Eulerian, which is checkable in linear time.

Why this matters in Data Science

DNA fragment assembly (Eulerian), routing problems, TSP, web crawler design.

Mind Map

Visual structure of the concept

TRAVERSALS
├── Walk — anything
├── Trail — no repeated EDGE
├── Path — no repeated VERTEX
├── Circuit — closed trail
└── Cycle — closed path

EULERIAN (EDGES)
├── Uses every edge once
├── Connected + all even-degree ⇒ Eulerian circuit
└── Connected + exactly 2 odd-degree ⇒ Eulerian trail

HAMILTONIAN (VERTICES)
├── Visits every vertex once
├── No simple iff; NP-complete in general
├── Dirac:  δ(G) ≥ n/2
└── Ore:    deg(u)+deg(v) ≥ n for non-adjacent u,v

Exam Q&A

Part A (2 marks) and Part B (20 marks) style questions

Part A (2 marks each)

Q1. Difference between path and circuit. A path has no repeated vertex; a circuit is a closed trail (no repeated edge, but may repeat vertices in some texts; commonly defined as a closed walk with no repeated edges).

Q2. Define Eulerian circuit. A closed trail that uses every edge of the graph exactly once.

Q3. State Dirac's theorem. A simple graph on $n \ge 3$ vertices with minimum degree $\delta(G) \ge n/2$ has a Hamiltonian circuit.

Q4. Is every Eulerian graph Hamiltonian? No. Eulerian deals with edges, Hamiltonian with vertices; neither implies the other.

Part B (20 marks)

Q. Distinguish between Eulerian and Hamiltonian graphs. State and prove Euler's theorem for an Eulerian circuit. Hence verify whether $K_5$ has an Eulerian circuit and/or Hamiltonian circuit.

Comparison table.

Aspect	Eulerian	Hamiltonian
Visits	every edge once	every vertex once
Closed version	Eulerian circuit	Hamiltonian circuit
Necessary & sufficient	yes — Euler's theorem	none known (NP-complete)
Check complexity	$O(V + E)$	NP-complete

Euler's theorem. A connected graph $G$ has an Eulerian circuit iff every vertex has even degree.

(⇒) Necessity. Suppose an Eulerian circuit exists. Each time the circuit enters a vertex it must leave (since it's closed and uses each edge once). So edges at each vertex pair up — every degree is even.

(⇐) Sufficiency. Suppose $G$ is connected and every vertex has even degree. Start a trail $T$ at any vertex $v_0$ ; whenever you reach a vertex, an unused edge is available (since each vertex has even degree, an incoming unused edge implies an outgoing one) — until you return to $v_0$ , forming a circuit $C_0$ .

If $C_0$ uses all edges, done. Otherwise, since $G$ is connected, some vertex $u$ on $C_0$ has unused edges. Repeat the argument from $u$ , obtaining circuit $C_1$ . Splice $C_1$ into $C_0$ at $u$ . Repeat until all edges are used. The result is a single Eulerian circuit. ∎

$K_5$ — every vertex has degree 4 (even). Connected (complete). By Euler's theorem, $K_5$ has an Eulerian circuit.

Hamiltonian? Yes — visit the 5 vertices in any cyclic order $v_1 \to v_2 \to v_3 \to v_4 \to v_5 \to v_1$ . Every $K_n$ for $n \ge 3$ is Hamiltonian.

Graphs: Definition and Types Seven Bridges, Shortest Path and Travelling Salesman