Euler and Hamiltonian Paths

Introduction

Two famous problems in graph theory involve traversing graphs:

• Euler paths: Visit every edge exactly once
• Hamiltonian paths: Visit every vertex exactly once

These concepts have practical applications in routing, scheduling, and optimization.

Euler Paths and Circuits

Definitions

Euler Path: A path that uses every edge exactly once.

Euler Circuit (Euler Cycle): A circuit that uses every edge exactly once and returns to the starting vertex.

Historical Context

Seven Bridges of Königsberg (1736):

• Leonhard Euler solved this famous problem
• Asked: Can you cross all 7 bridges exactly once?
• Euler proved it’s impossible
• Founded graph theory

Example 1: Euler Circuit

Graph:

1 --- 2
|     |
4 --- 3

Euler circuit: 1 → 2 → 3 → 4 → 1

All edges used exactly once, returns to start.

Example 2: Euler Path (not circuit)

Graph:

1 --- 2 --- 3

Euler path: 1 → 2 → 3

All edges used exactly once, but doesn’t return to start.

Example 3: No Euler Path

Graph:

    2
   /|\
  1 3 4

No Euler path exists (we’ll see why below).

Euler’s Theorem

Theorem 1: Euler Circuit

A connected graph has an Euler circuit if and only if:

• Every vertex has even degree

Theorem 2: Euler Path

A connected graph has an Euler path if and only if:

• Exactly 0 or 2 vertices have odd degree

If 0 vertices have odd degree → Euler circuit exists If 2 vertices have odd degree → Euler path exists (between those two) If more than 2 have odd degree → No Euler path

Proof Intuition

Why even degrees for circuit?

• Every time you enter a vertex, you must leave it
• Each visit uses 2 edges (in and out)
• Total degree must be even

Why 2 odd degrees for path?

• Start and end vertices used odd number of times
• All other vertices entered and exited equal times

Examples with Verification

Example 1: Square

Graph:

1 --- 2
|     |
4 --- 3

Degrees: All vertices have degree 2 (even)

Conclusion: Euler circuit exists ✓

Circuit: 1 → 2 → 3 → 4 → 1

Example 2: Path Graph

Graph:

1 --- 2 --- 3 --- 4

Degrees: deg(1)=1, deg(2)=2, deg(3)=2, deg(4)=1

Two odd-degree vertices: 1 and 4

Conclusion: Euler path exists (from 1 to 4 or vice versa) ✓

Path: 1 → 2 → 3 → 4

Example 3: Star Graph

Graph:

    2
   /|\
  1 3 4
   \|
    5

Degrees: deg(2)=4, all others=1

Four odd-degree vertices: 1, 3, 4, 5

Conclusion: No Euler path ✗

Example 4: Complete Graph K₃

Graph:

  1
 / \
2---3

Degrees: All vertices have degree 2 (even)

Conclusion: Euler circuit exists ✓

Circuit: 1 → 2 → 3 → 1

Example 5: Complete Graph K₄

Graph: K₄ (all pairs connected)

Degrees: All vertices have degree 3 (odd)

Four odd-degree vertices

Conclusion: No Euler path ✗

Finding Euler Paths: Fleury’s Algorithm

Algorithm:

1. Start at a vertex with odd degree (if exists), otherwise any vertex
2. At each step, choose an edge that:
   • Hasn’t been used yet
   • Is NOT a bridge (unless no other choice)
3. Remove the edge after traversing
4. Repeat until all edges used

Time Complexity: O(E²)

Example: Applying Fleury’s Algorithm

Graph:

1 --- 2
| \\ /|
|  X |
| / \\|
4 --- 3

Check: All degrees are even (degree 4) → Euler circuit exists

Steps:

1. Start at 1
2. Go to 2 (edge {1,2})
3. Go to 3 (edge {2,3})
4. Go to 4 (edge {3,4})
5. Go to 1 (edge {4,1})
6. Continue visiting remaining edges…

Hamiltonian Paths and Circuits

Definitions

Hamiltonian Path: A path that visits every vertex exactly once.

Hamiltonian Circuit (Hamiltonian Cycle): A circuit that visits every vertex exactly once and returns to the starting vertex.

Example 1: Hamiltonian Circuit

Graph:

1 --- 2
|     |
4 --- 3

Hamiltonian circuit: 1 → 2 → 3 → 4 → 1

All vertices visited exactly once.

Example 2: Hamiltonian Path (not circuit)

Graph:

1 --- 2 --- 3 --- 4

Hamiltonian path: 1 → 2 → 3 → 4

All vertices visited exactly once.

Example 3: Graph with No Hamiltonian Circuit

Graph:

1 --- 2
|     |
3     4
|     |
5 --- 6

No Hamiltonian circuit exists (try all possibilities - none work).

Key Difference: Euler vs. Hamiltonian

Necessary Conditions for Hamiltonian Circuit

Note: These conditions are necessary but NOT sufficient!

1. Graph must be connected
2. Must have at least 3 vertices
3. No cut vertices (for circuits in certain cases)

These don’t guarantee a Hamiltonian circuit exists!

Sufficient Conditions: Dirac’s Theorem

Dirac’s Theorem (1952):

If G is a simple graph with n vertices (n ≥ 3) and every vertex has degree ≥ n/2, then G has a Hamiltonian circuit.

Example: Applying Dirac’s Theorem

Graph: K₅ (complete graph with 5 vertices)

• n = 5
• Every vertex has degree 4
• Check: 4 ≥ 5/2 = 2.5 ✓

Conclusion: Hamiltonian circuit exists ✓

Circuit: 1 → 2 → 3 → 4 → 5 → 1 (or any other ordering)

Sufficient Conditions: Ore’s Theorem

Ore’s Theorem (1960):

If G is a simple graph with n vertices (n ≥ 3) and for every pair of non-adjacent vertices u and v, deg(u) + deg(v) ≥ n, then G has a Hamiltonian circuit.

Note: Ore’s theorem is more general than Dirac’s theorem.

Example: Applying Ore’s Theorem

Graph with 5 vertices:

    1
   /|\
  2-+-3
   \|/
    4---5

• Check all non-adjacent pairs
• If their degree sum ≥ 5, Hamiltonian circuit exists

Examples: Hamiltonian Analysis

Example 1: Petersen Graph

Famous example: Has no Hamiltonian circuit

Degrees: All vertices degree 3 Vertices: 10

Dirac’s test: 3 ≥ 10/2 = 5? NO (Doesn’t tell us anything - theorem doesn’t apply)

Result: Through exhaustive checking, no Hamiltonian circuit.

Example 2: Complete Graph Kₙ

Always has Hamiltonian circuit for n ≥ 3

Example path in K₄: 1 → 2 → 3 → 4 → 1

Example 3: Cycle Graph Cₙ

Always has Hamiltonian circuit (the cycle itself!)

Example C₅: 1 → 2 → 3 → 4 → 5 → 1

Example 4: Complete Bipartite K₃,₃

Has Hamiltonian circuit

Partition: V₁ = {1,2,3}, V₂ = {A,B,C}

Circuit: 1 → A → 2 → B → 3 → C → 1

Traveling Salesman Problem (TSP)

Problem: Find shortest Hamiltonian circuit in a weighted graph.

Applications:

• Delivery routes
• Circuit board drilling
• DNA sequencing
• Tour planning

Complexity: NP-hard (no known polynomial algorithm)

Example:

Cities: A, B, C, D with distances Goal: Visit all cities and return with minimum total distance

Approach: Find all Hamiltonian circuits and choose shortest

Comparison Summary

Euler Circuits

Easy to check:

• Count vertex degrees
• All even → Euler circuit exists

Easy to find:

• Fleury’s algorithm
• Polynomial time

Applications:

• Route planning (mail delivery)
• Drawing without lifting pen
• Network traversal

Hamiltonian Circuits

Hard to check:

• No simple test
• Must try different paths

Hard to find:

• No known polynomial algorithm
• NP-complete problem

Applications:

• Traveling Salesman Problem
• Tour planning
• DNA sequencing

Practical Applications

Euler Paths

1. Snow plow routing: Clear all streets
2. Mail delivery: Cover all routes
3. Drawing puzzles: Draw figure without lifting pen

Hamiltonian Paths

1. TSP: Minimize travel distance
2. Scheduling: Visit all locations
3. Knight’s tour: Chess problem
4. DNA sequencing: Reconstruct sequence

Key Points for Exams

1. Euler path: visits every edge exactly once
2. Hamiltonian path: visits every vertex exactly once
3. Euler circuit exists ↔ all even degrees
4. Euler path exists ↔ exactly 2 odd-degree vertices
5. Checking Euler: easy (polynomial)
6. Checking Hamiltonian: hard (NP-complete)
7. Dirac’s theorem: deg(v) ≥ n/2 → Hamiltonian circuit
8. Ore’s theorem: generalization of Dirac’s
9. TSP: find shortest Hamiltonian circuit
10. Fleury’s algorithm: finds Euler path

Practice Problems

1. Does this graph have Euler circuit? 1---2---3---4 with 4---1

2. Graph has degrees: 2,2,2,2,3,3. Euler path or circuit?

3. Does complete graph K₆ have Hamiltonian circuit?

4. Can you draw a square without lifting pen or retracing? (Euler?)

5. Apply Dirac’s theorem to graph where all vertices have degree 5, n=8

6. What’s the difference between visiting all edges vs all vertices?

7. Does a tree with n vertices have Hamiltonian path?

8. Seven Bridges: If one bridge is added, can you cross all bridges once?

9. Give example of graph with Hamiltonian but no Euler circuit

10. Why is Hamiltonian circuit problem harder than Euler circuit?