10.1 Eulerian vs Hamiltonian Graphs: Existence Theorems & Characterizations

Back to Discrete Mathematics Notes

📚Module 10: Advanced Graph Theory: Trees, Planarity & ColoringTopic 10.1: Eulerian vs Hamiltonian Graphs⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: The Seven Bridges of Königsberg vs The Traveling Salesperson

Think of navigating a city network:

1. The Eulerian Challenge (Street Sweeper / Mail Carrier): You are driving a snowplow or postal van. You must drive down every single street (edge) in the city to clear the snow, without driving down any street twice. Can you start and return to the depot without repeating any street?
   • Euler solved this in 1736: every time you enter an intersection, you must leave it via another street ($+2$ edges). Therefore, an Euler tour is possible if and only if every single intersection has an EVEN number of connecting streets!
2. The Hamiltonian Challenge (The Traveling Salesperson): You are a traveling salesperson. You don't care about driving down every street; you only care about visiting every client city (vertex) exactly once and returning home!
3. The P vs NP Divide:
   • Eulerian: Inspecting vertex degrees takes $O(V + E)$ linear time in class $\mathbf{P}$.
   • Hamiltonian: Checking whether a general graph contains a Hamiltonian cycle is NP-Complete!

💻 Bridging to Computer Science: Genome Sequencing & PCB Drill Path Optimization

In computer systems:

• De Bruijn Graphs & DNA Assembly: Next-generation genome sequencing breaks DNA reads into $k$-mers, models them as edges in a De Bruijn graph, and reconstructs the chromosome by finding an Eulerian path!
• PCB Drilling & CNC Toolpaths: Industrial robotic drills minimize manufacturing time by computing a Hamiltonian Cycle (Traveling Salesperson Problem) across the coordinates of circuit board holes.
• Cryptographic Trapdoors: Hamiltonian cycle detection in hard graphs powers zero-knowledge proof protocols.

📑Table of Contents

• ⚡ The Classical Duality: Eulerian vs Hamiltonian
• 🏛️ Eulerian Characterization: Euler's Theorem (1736)
• 🎯 Hamiltonian Graphs: Dirac's & Ore's Sufficiency Theorems
• 📝 Step-by-Step Worked Examples
  • Example 1: Solving the Seven Bridges of Königsberg
  • Example 2: Testing Dirac's and Ore's Theorems on a Network
• 🎯 Exam & Interview Pitfall Check

---

⚡ The Classical Duality: Eulerian vs Hamiltonian

Eulerian Graphs (Edge-Centric) vs Hamiltonian Graphs (Vertex-Centric)

The fundamental computational divide between linear-time edge traversals and NP-complete vertex paths

Eulerian (Edges)

Eulerian Traversal

🌉

Dominant Architecture / DomainExhaustive Edge Coverage

• •Euler Trail: Traverses EVERY edge in G exactly once.
• •Euler Circuit (Tour): Closed trail traversing every edge, returning to start.
• •Necessary & Sufficient: Checked instantaneously by degree parities!
• •Complexity: Solvable in O(V + E) linear time (Hierholzer's Algorithm).

"Every bridge crossed once and only once."

Hamiltonian (Vertices)

Hamiltonian Traversal

🎯

Dominant Architecture / DomainExhaustive Vertex Coverage

• •Hamiltonian Path: Visits EVERY vertex in G exactly once.
• •Hamiltonian Cycle: Closed cycle visiting every vertex, returning to start.
• •No simple characterization: Only sufficient conditions (Dirac, Ore).
• •Complexity: NP-Complete! No known polynomial-time decision algorithm.

"Every city visited once and only once."

---

🏛️ Eulerian Characterization: Euler's Theorem (1736)

📖Definition 10.1: Eulerian Trails & Circuitsdefinition

Let $G = (V, E)$ be a connected graph:

1. An Euler Trail (or Eulerian Path) is a trail that visits every edge in $E$ exactly once.
2. An Euler Circuit (or Eulerian Tour) is a closed trail that visits every edge in $E$ exactly once and ends at the starting vertex.
3. A graph is called an Eulerian Graph if it possesses an Euler Circuit.

📐Theorem 10.1: Euler's Theorem for Eulerian Graphstheorem

Let $G = (V, E)$ be a connected undirected graph:

1. Euler Circuit Criterion: $G$ contains an Euler Circuit if and only if EVERY vertex in $G$ has an EVEN degree: $$\forall v \in V, \quad \deg(v) \equiv 0 \pmod 2$$
2. Euler Trail Criterion: $G$ contains an Euler Trail (but not a circuit) if and only if EXACTLY TWO vertices in $G$ have ODD degree: $$|\{ v \in V \mid \deg(v) \text{ is odd} \}| = 2$$ (The Euler trail must start at one of the odd-degree vertices and terminate at the other odd-degree vertex).

If a connected graph has more than 2 odd-degree vertices (e.g. 4, 6, 8...), it can have neither an Euler trail nor an Euler circuit!

The 3-Step Decision Flow for Eulerian Graphs

Instant verification checklist to determine trail or circuit existence

1

Check Graph Connectivity

Pre-Condition

Ensure all vertices with non-zero degree belong to a single connected component. (Isolated vertices of degree 0 are ignored).

2

Count Odd-Degree Vertices

Parity Check

Count the number of vertices k with odd degree: k = |{ v | deg(v) is odd }|.

3

Classify Traversal Status

Classification

If k = 0 ⟹ Euler Circuit! If k = 2 ⟹ Euler Trail (starts at odd 1, ends at odd 2). If k > 2 ⟹ Zero Eulerian traversals possible!

✓ Eulerian Refutation: 4 Odd Vertices

The Seven Bridges of Königsberg: All 4 landmasses have odd degrees (5, 3, 3, 3), proving by Euler’s Theorem that zero Eulerian paths or circuits can exist.

---

🎯 Hamiltonian Graphs: Dirac's & Ore's Sufficiency Theorems

📖Definition 10.2: Hamiltonian Paths & Cyclesdefinition

Let $G = (V, E)$ be a graph:

1. A Hamiltonian Path is a simple path that visits every vertex in $V$ exactly once.
2. A Hamiltonian Cycle is a closed simple cycle that visits every vertex in $V$ exactly once and returns to the starting vertex.
3. A graph is called a Hamiltonian Graph if it contains a Hamiltonian Cycle.

Unlike Eulerian graphs, there is no known necessary and sufficient condition that characterizes all Hamiltonian graphs in polynomial time.

📐Theorem 10.2: Dirac's Theorem (1952)theorem

If $G = (V, E)$ is a simple graph with $n \ge 3$ vertices such that the degree of every vertex is at least half the total number of vertices:

$$\forall v \in V, \quad \deg(v) \ge \frac{n}{2}$$

then $G$ is guaranteed to be Hamiltonian!

(Note: Dirac's condition is a sufficient condition, not a necessary one. A graph can be Hamiltonian even if some vertices have degree $< n/2$; for example, cycle $C_n$ is Hamiltonian for all $n \ge 3$, yet every vertex has degree $2 < n/2$ for $n \ge 5$).

📐Theorem 10.3: Ore's Theorem (1960)theorem

If $G = (V, E)$ is a simple graph with $n \ge 3$ vertices such that for every pair of non-adjacent vertices $u$ and $v$:

$$\deg(u) + \deg(v) \ge n$$

then $G$ is guaranteed to be Hamiltonian!

Relationship: Dirac's Theorem is a direct special case of Ore's Theorem: if $\deg(u) \ge n/2$ and $\deg(v) \ge n/2$, then $\deg(u) + \deg(v) \ge n/2 + n/2 = n$.

---

📝 Step-by-Step Worked Examples

Example 1: Solving the Seven Bridges of Königsberg

Problem Statement: The city of Königsberg had 4 landmasses ($A, B, C, D$) connected by 7 bridges across the Pregel River:

• Landmass $A$ connects to $B$ (2 bridges), $C$ (2 bridges), and $D$ (1 bridge).
• Landmass $B$ connects to $A$ (2 bridges) and $D$ (1 bridge).
• Landmass $C$ connects to $A$ (2 bridges) and $D$ (1 bridge).
• Landmass $D$ connects to $A$ (1 bridge), $B$ (1 bridge), and $C$ (1 bridge).

Can a citizen take a continuous walk that crosses every single bridge exactly once?

Step-by-Step Solution:

1. Step 1: Calculate the Degree of Each Landmass (Vertex)

   • $\deg(A) = 2 + 2 + 1 = 5$ (Odd!)
   • $\deg(B) = 2 + 1 = 3$ (Odd!)
   • $\deg(C) = 2 + 1 = 3$ (Odd!)
   • $\deg(D) = 1 + 1 + 1 = 3$ (Odd!)

2. Step 2: Apply Euler's Theorem

   • The graph has $n = 4$ vertices, and ALL 4 vertices have odd degrees!
   • By Theorem 10.1:
     • An Euler circuit requires 0 odd vertices.
     • An Euler trail requires exactly 2 odd vertices.
   • Since the graph has 4 odd vertices, NO Eulerian trail or circuit exists!
   • Conclusion: It is mathematically impossible to cross all 7 bridges without crossing at least one bridge twice!

Key Takeaway: Euler's resolution of the Königsberg bridge problem birthed the entire field of Graph Theory by abstracting physical geometry into vertex degrees.

---

Example 2: Testing Dirac's and Ore's Theorems on a Network

Problem Statement: A network has $n = 6$ servers. The degree sequence is $(4, 4, 3, 3, 3, 3)$.

1. Does this graph satisfy Dirac's Theorem?
2. If the two degree-4 vertices are connected to each other, and all non-adjacent pairs satisfy $\deg(u) + \deg(v) \ge 6$, does it satisfy Ore's Theorem? Is it Hamiltonian?

Step-by-Step Solution:

1. Part 1: Testing Dirac's Condition

   • Number of vertices: $n = 6$.
   • Dirac threshold: $\frac{n}{2} = \frac{6}{2} = 3$.
   • The minimum degree in the graph is $\delta(G) = 3$.
   • Since every vertex has degree $\deg(v) \ge 3 \ge n/2$: $$\forall v \in V, \quad \deg(v) \ge 3 = \frac{n}{2}$$
   • Yes, it satisfies Dirac's Theorem!
   • Therefore, the graph is guaranteed to be Hamiltonian.

2. Part 2: Testing Ore's Condition

   • For every non-adjacent pair $u, v$, the minimum possible degree sum is: $$\deg(u) + \deg(v) \ge 3 + 3 = 6 = n$$
   • Since the sum of degrees for every non-adjacent pair is $\ge n = 6$, Ore's condition is fully satisfied.
   • Both theorems confirm the existence of a Hamiltonian Cycle.

Key Takeaway: Checking $\delta(G) \ge n/2$ provides a 1-second verification of Hamiltonicity in dense networks.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Can a bipartite graph with an odd number of vertices ever be Hamiltonian? Key Focus Points: Never! In a bipartite graph $G = (V_1 \cup V_2, E)$, any cycle must alternate between $V_1$ and $V_2$ at every step ($v_1 \to v_2 \to v_1 \to v_2 \dots$). Therefore, any cycle in a bipartite graph must have an even length! A Hamiltonian cycle visits all $n$ vertices, so its length is $n$. If $n$ is odd, no Hamiltonian cycle can exist! Furthermore, even if $n$ is even, a bipartite graph is Hamiltonian only if $|V_1| = |V_2|$.

Question 2: Is a complete graph $K_n$ always Eulerian? Always Hamiltonian? Key Focus Points:

• Hamiltonian: $K_n$ is ALWAYS Hamiltonian for all $n \ge 3$ (Dirac's condition $\deg(v) = n - 1 \ge n/2$ holds).
• Eulerian: In $K_n$, every vertex has degree $n - 1$. For $K_n$ to have an Euler circuit, $n - 1$ must be even, which means $n$ must be an ODD number! (e.g. $K_3, K_5, K_7$ are Eulerian; $K_4, K_6$ are NOT Eulerian).

Common Interview Traps: Architectural Trade-Offs

Trap 1: Assuming Dirac's condition is necessary Why it fails: Students often claim: "$\delta(G) < n/2$, so the graph is not Hamiltonian." This is completely false! Cycle graph $C_{100}$ has 100 vertices and is obviously Hamiltonian, yet every vertex has degree $2 \ll 50$. Dirac is only a sufficient condition!

Trap 2: Forgetting to check connectivity for Euler's Theorem Why it fails: If a graph consists of two disjoint cycles $C_3$ and $C_3$, every vertex has degree 2 (even), but the graph is disconnected! An Euler tour cannot jump between disjoint components. Euler's theorem strictly requires that all edges lie in a single connected component.

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic9.3 Walks, Paths, Cycles, Connectivity & Cut-Vertex InvariantsNext Topic →10.2 Trees, Properties of Spanning Trees & Cayley's Formula