Data Structures & AlgorithmsAdvanced Graph Patterns

Advanced Graph Patterns: Classical Problems & Computational Boundaries

LevelAdvanced

Duration90 mins

TopicAdvanced Graph Patterns

1 / 4

Eulerian and Hamiltonian Paths: Two Sides of Graph Traversal

The Two Fundamental Traversal Problems

Graph theory presents two seemingly similar questions that lie at the heart of discrete mathematics and computer science:

Question 1: Can we traverse every edge of a graph exactly once, returning to our starting point?

Question 2: Can we visit every vertex of a graph exactly once, returning to our starting point?

These questions appear nearly identical—one focuses on edges, the other on vertices. Yet their computational complexity differs dramatically. The first question can be answered in polynomial time with a simple characterization. The second is one of the most famous unsolved problems in computer science, belonging to the class of NP-complete problems.

Understanding why these similar-sounding problems have such different complexities provides profound insight into the nature of computation itself.

What You Will Master

By the end of this page, you will understand: (1) The precise definitions of Eulerian and Hamiltonian paths/circuits, (2) The elegant mathematical characterization that makes Eulerian problems tractable, (3) Why no such characterization exists for Hamiltonian problems, (4) Algorithms for finding Eulerian paths, and (5) The broader implications for recognizing tractable vs. intractable problems.

Historical Origins: The Königsberg Bridge Problem

The study of Eulerian paths begins with one of the most celebrated problems in the history of mathematics: the Seven Bridges of Königsberg.

The Setting (1736):

Königsberg (now Kaliningrad, Russia) was built on the Pregel River, which contained two islands. The islands were connected to each other and the mainland by seven bridges. Citizens of Königsberg posed a recreational question: Could one walk through the city, crossing each bridge exactly once, and return to the starting point?

Euler's Revolutionary Insight:

Leonhard Euler approached this problem not by attempting various routes, but by abstracting it into what we now call a graph. He represented:

Each landmass (two banks and two islands) as a vertex (node)
Each bridge as an edge connecting two vertices

This abstraction transformed a geographic puzzle into a purely mathematical question about graph structure. More importantly, Euler proved that the specific route doesn't matter—only the structure of connections determines whether such a walk exists.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
                    Königsberg Graph Representation
               =========================================
               
               The city layout:                     The abstracted graph:
               
                    North Bank                           A (North Bank)
                   /    |    \                          /|\
                 [1]   [2]   [3]                       / | \
                 /      |      \                     e1 e2 e3
                Island C ---- Island D              /   |   \
                   \     [7]    /                  C----e7---D
                   [4]        [5]                   \   |   /
                     \   [6]   /                    e4 e6 e5
                      \   |   /                      \ | /
                     South Bank                        B (South Bank)
               
               Vertices: A (North), B (South), C (Island), D (Island)
               Edges: 7 bridges connecting the landmasses
               
               Degree of each vertex:
               - A (North Bank): 3 bridges → degree 3
               - B (South Bank): 3 bridges → degree 3  
               - C (Island): 3 bridges → degree 3
               - D (Island): 3 bridges → degree 3
               
               All vertices have ODD degree!

Euler's Theorem (1736):

Euler discovered that an Eulerian circuit (a closed walk traversing every edge exactly once) exists if and only if:

The graph is connected (all vertices can reach all others)
Every vertex has even degree

Since all four vertices in the Königsberg graph have odd degree (3), no Eulerian circuit exists. Euler proved this impossible—not by exhaustive search, but by pure logical reasoning.

This 1736 paper is widely considered the birth of both graph theory and topology, making it one of the most important papers in the history of mathematics.

The Power of Abstraction

Euler's insight exemplifies the power of mathematical abstraction. By ignoring irrelevant details (bridge lengths, island shapes, walking speed) and focusing on structure (what connects to what), he transformed an impossible enumeration problem into a simple counting problem. This abstraction principle underlies all of computer science.

Formal Definitions: Paths, Circuits, and Trails

Before diving deeper, we need precise definitions. Graph theory terminology can be confusing because different authors use terms differently. Here we establish rigorous definitions:

Basic Walk Terminology:

Walk: A sequence of vertices where consecutive vertices are connected by edges. Vertices and edges may repeat.
Trail: A walk where no edge repeats (but vertices may repeat).
Path: A walk where no vertex repeats (and thus no edge repeats).
Closed Walk/Circuit: A walk that starts and ends at the same vertex.
Cycle: A closed path (no repeated vertices except start = end).

Walk Types and Their Constraints
Type	Edge Repetition	Vertex Repetition	Returns to Start
Walk	Allowed	Allowed	May or may not
Trail	Not allowed	Allowed	May or may not
Path	Not allowed	Not allowed	No
Circuit	Allowed	Allowed	Yes (by definition)
Eulerian Trail	Not allowed (visits each once)	Allowed	No
Eulerian Circuit	Not allowed (visits each once)	Allowed	Yes
Hamiltonian Path	Not allowed	Not allowed (visits each once)	No
Hamiltonian Cycle	Not allowed	Not allowed (visits each once)	Yes

Eulerian Definitions:

Eulerian Trail (Eulerian Path): A trail that visits every edge of the graph exactly once. Does not need to return to the starting vertex.
Eulerian Circuit (Eulerian Cycle): A trail that visits every edge exactly once and returns to the starting vertex. This is a closed Eulerian trail.
Eulerian Graph: A graph that contains an Eulerian circuit.
Semi-Eulerian Graph: A graph that contains an Eulerian trail but not an Eulerian circuit.

Hamiltonian Definitions:

Hamiltonian Path: A path that visits every vertex of the graph exactly once.
Hamiltonian Cycle: A cycle that visits every vertex exactly once and returns to the starting vertex.
Hamiltonian Graph: A graph that contains a Hamiltonian cycle.

Critical Distinction

The key difference: Eulerian problems ask about traversing EDGES; Hamiltonian problems ask about visiting VERTICES. This seemingly small distinction creates an enormous gap in computational complexity. Always clarify which problem you're solving.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
    Consider this graph:
    
         A ------- B
         |\       /|
         | \     / |
         |  \   /  |
         |   \ /   |
         |    X    |
         |   / \   |
         |  /   \  |
         | /     \ |
         |/       \|
         D ------- C
    
    Edges: A-B, A-C, A-D, B-C, B-D, C-D (6 edges = K4, complete graph on 4 vertices)
    
    EULERIAN CIRCUIT (traverse each edge once, return to start):
    --------------------------------------------------------
    A → B → C → D → A → C → B → D → A
    
    Wait, this visits edges: A-B, B-C, C-D, D-A, A-C, C-B, B-D, D-A
    But we have duplicates! Let's try again...
    
    A → B → C → A → D → B → C → D → A  ❌ Still not right
    
    Actually, K4 has 6 edges. Each vertex has degree 3 (odd).
    By Euler's theorem: NO Eulerian circuit exists in K4!
    
    HAMILTONIAN CYCLE (visit each vertex once, return to start):
    -----------------------------------------------------------
    A → B → C → D → A  ✓
    
    This visits each vertex exactly once and returns to start.
    K4 definitely has Hamiltonian cycles!
    
    KEY INSIGHT: A graph can have Hamiltonian cycles without Eulerian circuits!

Euler's Theorems: Complete Characterization

The beauty of Eulerian problems lies in their complete characterization. We can determine whether an Eulerian path or circuit exists by simply counting vertex degrees—no search required.

Theorem 1 (Eulerian Circuit):

A connected graph G has an Eulerian circuit if and only if every vertex has even degree.

Theorem 2 (Eulerian Trail):

A connected graph G has an Eulerian trail (but not an Eulerian circuit) if and only if it has exactly two vertices of odd degree. The trail must start at one odd-degree vertex and end at the other.

Theorem 3 (Impossibility):

If a connected graph has more than two vertices of odd degree, no Eulerian trail or circuit exists.

Why These Theorems Work

•Even Degree Necessity: When we traverse a vertex (neither starting nor ending), we enter via one edge and leave via another. Each traversal 'uses' two edges. For all edges to be used exactly once, we need an even number of edges at each vertex.
•Odd Vertices Must Be Endpoints: At the start vertex, we leave (use one edge) before any entry. At the end vertex, we enter (use one edge) with no exit. These vertices use an odd number of edges. All other vertices must use an even number.
•Exactly Two or Zero: Since every edge connects exactly two vertices, the sum of all degrees equals 2|E| (even). Thus, the number of odd-degree vertices must be even. Combined with the endpoint argument: either 0 (circuit) or 2 (trail) odd vertices.
•The Handshaking Lemma: The sum of all vertex degrees equals 2 × (number of edges). This fundamental lemma underlies the entire theory.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
interface Graph {
    vertices: number;          // Number of vertices (0 to V-1)
    adjacencyList: number[][]; // adjacencyList[v] = list of neighbors
}
 
enum EulerianType {
    NOT_EULERIAN = "No Eulerian path or circuit exists",
    EULERIAN_PATH = "Eulerian path exists (but not circuit)",
    EULERIAN_CIRCUIT = "Eulerian circuit exists"
}
 
/**
 * Determines if a graph has an Eulerian path, circuit, or neither.
 * Time Complexity: O(V + E) - we traverse the adjacency list once
 * Space Complexity: O(1) - only storing counts
 */
function classifyEulerian(graph: Graph): EulerianType {
    // Step 1: Check connectivity (required for both path and circuit)
    if (!isConnected(graph)) {
        // Exception: isolated vertices (degree 0) don't affect Eulerian properties
        // A more precise check would ignore isolated vertices
        return EulerianType.NOT_EULERIAN;
    }
    
    // Step 2: Count vertices with odd degree
    let oddDegreeCount = 0;
    
    for (let v = 0; v < graph.vertices; v++) {
        const degree = graph.adjacencyList[v].length;
        if (degree % 2 !== 0) {
            oddDegreeCount++;
        }
    }
    
    // Step 3: Apply Euler's theorem
    if (oddDegreeCount === 0) {
        // All vertices have even degree → Eulerian circuit exists
        return EulerianType.EULERIAN_CIRCUIT;
    } else if (oddDegreeCount === 2) {
        // Exactly two vertices have odd degree → Eulerian path exists
        return EulerianType.EULERIAN_PATH;
    } else {
        // More than two odd-degree vertices → impossible
        return EulerianType.NOT_EULERIAN;
    }
}
 
/**
 * Check if graph is connected using DFS
 * Ignores isolated vertices (vertices with degree 0)
 */
function isConnected(graph: Graph): boolean {
    // Find a vertex with non-zero degree to start
    let startVertex = -1;
    let nonIsolatedCount = 0;
    
    for (let v = 0; v < graph.vertices; v++) {
        if (graph.adjacencyList[v].length > 0) {
            nonIsolatedCount++;
            if (startVertex === -1) {
                startVertex = v;
            }
        }
    }
    
    // If no edges exist, trivially "connected" (or empty)
    if (startVertex === -1) {
        return true;
    }
    
    // DFS to count reachable non-isolated vertices
    const visited = new Set<number>();
    const stack = [startVertex];
    
    while (stack.length > 0) {
        const current = stack.pop()!;
        if (visited.has(current)) continue;
        visited.add(current);
        
        for (const neighbor of graph.adjacencyList[current]) {
            if (!visited.has(neighbor)) {
                stack.push(neighbor);
            }
        }
    }
    
    // Check if all non-isolated vertices were reached
    return visited.size === nonIsolatedCount;
}
 
// Example usage with the Königsberg bridge graph
const konigsbergGraph: Graph = {
    vertices: 4,  // A=0 (North), B=1 (South), C=2 (Island1), D=3 (Island2)
    adjacencyList: [
        [2, 2, 3],      // A connects to C (2 bridges) and D (1 bridge)
        [2, 2, 3],      // B connects to C (2 bridges) and D (1 bridge)
        [0, 0, 1, 1, 3], // C connects to A (2), B (2), D (1)
        [0, 1, 2]        // D connects to A (1), B (1), C (1)
    ]
};
 
console.log(classifyEulerian(konigsbergGraph)); 
// Output: "No Eulerian path or circuit exists"
// All 4 vertices have odd degree (3, 3, 5, 3)

The Elegance of Characterization

Notice the profound simplicity: to solve the Eulerian problem, we don't search for paths at all. We count degrees. This O(V + E) degree-counting provides a complete answer to a question that might naively seem to require exponential enumeration. This is what a 'good characterization' means in complexity theory.

Hierholzer's Algorithm: Finding Eulerian Circuits

Once we've determined that an Eulerian circuit exists, how do we actually find it? Hierholzer's algorithm (1873) provides an elegant O(E) solution.

The Core Insight:

If we start at any vertex and follow edges (removing them as we go), we must eventually return to the start vertex—because every vertex has even degree. This creates a circuit, but not necessarily an Eulerian circuit (we might not have used all edges).

However, if there are unused edges, they must be attached to some vertex on our current circuit (since the graph is connected). We can find such a vertex, construct another circuit from it, and splice it into our main circuit.

Repeating this process until all edges are used gives us the complete Eulerian circuit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/**
 * Hierholzer's Algorithm for finding an Eulerian Circuit
 * 
 * Precondition: Graph must have an Eulerian circuit
 *               (connected, all vertices have even degree)
 * 
 * Time Complexity: O(E) - each edge is visited exactly once
 * Space Complexity: O(E) - for the result path and stack
 */
function findEulerianCircuit(
    numVertices: number,
    edges: [number, number][] // List of edges as [u, v] pairs
): number[] {
    // Build adjacency list with edge indices for efficient removal
    // Using a Map to track remaining edges at each vertex
    const adj: Map<number, number[]>[] = Array.from(
        { length: numVertices },
        () => new Map()
    );
    
    // For undirected graph, each edge appears in both directions
    // We use an index to track which edges have been used
    const edgeUsed: boolean[] = new Array(edges.length).fill(false);
    
    for (let i = 0; i < edges.length; i++) {
        const [u, v] = edges[i];
        // Store edge index at both endpoints
        if (!adj[u].has(v)) adj[u].set(v, []);
        if (!adj[v].has(u)) adj[v].set(u, []);
        adj[u].get(v)!.push(i);
        adj[v].get(u)!.push(i);
    }
    
    const circuit: number[] = [];
    const stack: number[] = [0]; // Start from vertex 0
    
    // Track current position in each vertex's neighbor list
    const pointers: Map<number, number>[] = adj.map(
        neighbors => new Map([...neighbors.keys()].map(k => [k, 0]))
    );
    
    while (stack.length > 0) {
        const current = stack[stack.length - 1];
        
        // Find an unused edge from current vertex
        let foundEdge = false;
        
        for (const [neighbor, edgeIndices] of adj[current]) {
            // Try to find an unused edge to this neighbor
            while (pointers[current].get(neighbor)! < edgeIndices.length) {
                const edgeIdx = edgeIndices[pointers[current].get(neighbor)!];
                pointers[current].set(neighbor, pointers[current].get(neighbor)! + 1);
                
                if (!edgeUsed[edgeIdx]) {
                    edgeUsed[edgeIdx] = true;
                    stack.push(neighbor);
                    foundEdge = true;
                    break;
                }
            }
            if (foundEdge) break;
        }
        
        if (!foundEdge) {
            // No more unused edges from this vertex
            // Add it to the circuit (in reverse order)
            circuit.push(stack.pop()!);
        }
    }
    
    // Circuit is built in reverse
    circuit.reverse();
    return circuit;
}
 
// Simplified version using adjacency list with degree tracking
function findEulerianCircuitSimple(adjacencyList: number[][]): number[] {
    // Clone the adjacency list since we'll modify it
    const adj = adjacencyList.map(neighbors => [...neighbors]);
    
    const circuit: number[] = [];
    const stack: number[] = [0];
    
    while (stack.length > 0) {
        const current = stack[stack.length - 1];
        
        if (adj[current].length > 0) {
            // Take an edge from current to a neighbor
            const next = adj[current].pop()!;
            
            // Remove the reverse edge (for undirected graph)
            const reverseIdx = adj[next].indexOf(current);
            if (reverseIdx !== -1) {
                adj[next].splice(reverseIdx, 1);
            }
            
            stack.push(next);
        } else {
            // No more edges from this vertex
            circuit.push(stack.pop()!);
        }
    }
    
    return circuit.reverse();
}
 
// Example: Find Eulerian circuit in a house-shaped graph
//       0
//      /|\
//     1-+-2
//     | X |
//     |/ \|
//     3---4
 
const houseGraph = [
    [1, 2],           // 0 connects to 1, 2
    [0, 2, 3, 4],     // 1 connects to 0, 2, 3, 4
    [0, 1, 3, 4],     // 2 connects to 0, 1, 3, 4
    [1, 2, 4],        // 3 connects to 1, 2, 4
    [1, 2, 3]         // 4 connects to 1, 2, 3
];
 
// Wait - let's verify: degrees are 2, 4, 4, 3, 3
// Vertices 3 and 4 have odd degree! This has Eulerian PATH, not circuit.
 
// Correct example - add edge between 3 and 4 to make all even:
const eulerianGraph = [
    [1, 2],               // Degree 2 (even)
    [0, 2, 3, 4],         // Degree 4 (even)
    [0, 1, 3, 4],         // Degree 4 (even)
    [1, 2, 4, 4],         // Degree 4 (even) - two edges to 4
    [1, 2, 3, 3]          // Degree 4 (even) - two edges to 3
];
 
console.log(findEulerianCircuitSimple(eulerianGraph));
// Possible output: [0, 1, 3, 4, 3, 2, 4, 1, 2, 0]

Algorithm Walkthrough:

Start anywhere (for a circuit, any vertex works)
Traverse edges greedily, marking each as used
When stuck (no unused edges from current vertex), backtrack and record the vertex
Continue until stack is empty
Reverse the recorded sequence to get the Eulerian circuit

Why This Works:

The key insight is that when we backtrack and record a vertex, all edges incident to that vertex have been used. When we reach the starting vertex with no remaining edges, we've completed the circuit. The reversal corrects the order since we record vertices when leaving them, not when entering.

Handling Eulerian Paths

For an Eulerian PATH (exactly two odd-degree vertices), simply start from one of the odd-degree vertices. The same algorithm will find the path, ending at the other odd-degree vertex. You can also add a temporary edge between the two odd vertices, find the circuit, and remove that edge from the result.

Hamiltonian Problems: A Fundamentally Different Beast

Now we turn to Hamiltonian paths and cycles—problems that look superficially similar to Eulerian problems but are fundamentally different.

The Hamiltonian Cycle Problem:

Given a graph G, does there exist a cycle that visits every vertex exactly once?

The Stark Contrast with Eulerian Problems:

For Eulerian problems, we have a complete characterization: count vertex degrees, and you know the answer. For Hamiltonian problems, no such simple characterization exists. Despite centuries of effort by brilliant mathematicians and computer scientists, we cannot determine if a graph has a Hamiltonian cycle without, in the worst case, essentially trying all possibilities.

This isn't just because we haven't been clever enough—it's believed to be fundamentally impossible for polynomial-time algorithms.

Eulerian Problems

•Complete characterization exists (degree parity)
•O(V + E) to determine existence
•O(E) to find the actual path/circuit
•Simple necessary and sufficient conditions
•No search required—just count
•Solved elegantly in 1736 by Euler

Hamiltonian Problems

•No known characterization exists
•NP-complete to determine existence
•Exponential time required in worst case
•Only sufficient conditions (not necessary)
•May require exhaustive search
•Unsolved for polynomial time since defined

Why Is Hamiltonian So Much Harder?

The fundamental difference stems from the global nature of the Hamiltonian constraint versus the local nature of the Eulerian constraint:

Eulerian (local): Each edge must be traversed once. This constraint is satisfied by ensuring local conditions at each vertex (even degree). There's no "interaction" between distant parts of the graph.
Hamiltonian (global): Each vertex must appear exactly once in the path. This creates complex dependencies: visiting vertex A early might block access to vertex B later, even if they're not directly connected. The constraint propagates through the entire graph structure.

No local characterization can capture these global dependencies. The only way to verify is to consider the entire path structure—and there are potentially V! orderings to check.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    Consider finding a Hamiltonian path in a complete graph Kn:
    
    n = 5 vertices:
    - Possible orderings: 5! = 120
    - Easily checkable by computer
    
    n = 10 vertices:
    - Possible orderings: 10! = 3,628,800
    - Still manageable
    
    n = 20 vertices:
    - Possible orderings: 20! ≈ 2.4 × 10^18
    - Would take centuries for brute force
    
    n = 50 vertices:
    - Possible orderings: 50! ≈ 3 × 10^64
    - More than atoms in the observable universe
    
    Contrast with Eulerian:
    - For ANY n, just count degrees: O(n) operations
    - No explosion of possibilities
    
    This is the essence of the P vs NP distinction.

Sufficient Conditions for Hamiltonian Cycles

While we lack necessary and sufficient conditions for Hamiltonicity, mathematicians have discovered several sufficient conditions—conditions that, if satisfied, guarantee a Hamiltonian cycle exists (though the graph might have one even if they're not satisfied).

Theorem (Dirac, 1952):

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

Theorem (Ore, 1960):

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

Special Cases:

Complete graphs Kn (n ≥ 3): Always Hamiltonian
Complete bipartite graphs Km,n (m = n): Always Hamiltonian
Hypercubes Qn: Always Hamiltonian for n ≥ 2

Sufficient ≠ Necessary

These conditions are NOT necessary! Many graphs with Hamiltonian cycles fail these conditions. A cycle graph Cn has degree 2 at every vertex, far below n/2, yet it's trivially Hamiltonian. Failing these tests proves nothing about non-existence.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/**
 * Backtracking algorithm to find a Hamiltonian cycle
 * 
 * Time Complexity: O(n!) worst case - exponential
 * Space Complexity: O(n) for the path and recursion stack
 * 
 * This demonstrates the computational difficulty of Hamiltonian problems.
 */
function findHamiltonianCycle(adjacencyList: number[][]): number[] | null {
    const n = adjacencyList.length;
    if (n < 3) return null; // Need at least 3 vertices for a cycle
    
    const path: number[] = new Array(n).fill(-1);
    const visited: boolean[] = new Array(n).fill(false);
    
    // Start from vertex 0
    path[0] = 0;
    visited[0] = true;
    
    function backtrack(pos: number): boolean {
        // Base case: all vertices are in the path
        if (pos === n) {
            // Check if there's an edge from last vertex back to first
            const lastVertex = path[n - 1];
            const firstVertex = path[0];
            return adjacencyList[lastVertex].includes(firstVertex);
        }
        
        // Try each vertex as the next in the path
        for (const nextVertex of adjacencyList[path[pos - 1]]) {
            if (!visited[nextVertex]) {
                // Choose
                path[pos] = nextVertex;
                visited[nextVertex] = true;
                
                // Explore
                if (backtrack(pos + 1)) {
                    return true;
                }
                
                // Unchoose (backtrack)
                visited[nextVertex] = false;
                path[pos] = -1;
            }
        }
        
        return false;
    }
    
    if (backtrack(1)) {
        return path;
    }
    return null;
}
 
// Optimized version with pruning
function findHamiltonianCycleOptimized(adjacencyList: number[][]): number[] | null {
    const n = adjacencyList.length;
    if (n < 3) return null;
    
    // Precompute for pruning: if any vertex becomes unreachable, abort
    const path: number[] = [0];
    const visited: boolean[] = new Array(n).fill(false);
    visited[0] = true;
    
    function canComplete(path: number[]): boolean {
        // Early pruning: check if remaining vertices are still reachable
        const remaining = n - path.length;
        if (remaining === 0) return true;
        
        // Check if every unvisited vertex has at least one unvisited neighbor
        // (or is connected to path endpoint)
        for (let v = 0; v < n; v++) {
            if (!visited[v]) {
                let hasConnection = false;
                for (const neighbor of adjacencyList[v]) {
                    if (!visited[neighbor] || neighbor === path[path.length - 1]) {
                        hasConnection = true;
                        break;
                    }
                }
                if (!hasConnection && remaining > 1) return false;
            }
        }
        return true;
    }
    
    function backtrack(): boolean {
        if (path.length === n) {
            return adjacencyList[path[n - 1]].includes(0);
        }
        
        const current = path[path.length - 1];
        
        // Sort neighbors by degree (choose most constrained first - heuristic)
        const neighbors = [...adjacencyList[current]]
            .filter(v => !visited[v])
            .sort((a, b) => {
                const degA = adjacencyList[a].filter(x => !visited[x]).length;
                const degB = adjacencyList[b].filter(x => !visited[x]).length;
                return degA - degB; // Most constrained first
            });
        
        for (const next of neighbors) {
            path.push(next);
            visited[next] = true;
            
            if (canComplete(path) && backtrack()) {
                return true;
            }
            
            visited[next] = false;
            path.pop();
        }
        
        return false;
    }
    
    if (backtrack()) {
        return path;
    }
    return null;
}
 
// Example: Pentagon graph (cycle of 5)
const pentagon = [
    [1, 4],  // 0
    [0, 2],  // 1
    [1, 3],  // 2
    [2, 4],  // 3
    [3, 0]   // 4
];
 
console.log(findHamiltonianCycle(pentagon)); 
// Output: [0, 1, 2, 3, 4] - trivially Hamiltonian since it's a cycle

Directed Graphs and Variations

Both Eulerian and Hamiltonian concepts extend to directed graphs with modified conditions.

Eulerian Circuits in Directed Graphs:

A strongly connected directed graph has an Eulerian circuit if and only if:

Every vertex has in-degree equal to out-degree

For an Eulerian path (not circuit):

At most one vertex has out-degree = in-degree + 1 (start vertex)
At most one vertex has in-degree = out-degree + 1 (end vertex)
All other vertices have in-degree = out-degree

Common Applications:

Real-World Applications of Eulerian and Hamiltonian Concepts
Problem	Graph Type	Concept	Application
DNA Fragment Assembly	Directed	Eulerian Path	De Bruijn graphs for genome sequencing
Chinese Postman Problem	Undirected/Directed	Eulerian Path	Minimum-distance route covering all streets
Traveling Salesman	Complete + Weights	Hamiltonian Cycle	Minimum-cost tour visiting all cities
Knight's Tour	Undirected	Hamiltonian Path	Chess knight visiting all squares once
Circuit Board Testing	Directed	Eulerian Path	Testing all connections with one probe run
Gray Code Generation	Hypercube	Hamiltonian Cycle	Binary counting with single-bit changes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/**
 * Find Eulerian path in directed graph
 * Used in DNA fragment assembly via de Bruijn graphs
 * 
 * The de Bruijn graph approach:
 * 1. Break DNA reads into k-mers (length k substrings)
 * 2. Create vertices for (k-1)-mers
 * 3. Create edges for k-mers connecting their prefix to suffix
 * 4. Find Eulerian path to reconstruct the original sequence
 */
interface DirectedGraph {
    vertices: number;
    adjacencyList: number[][];  // outgoing edges only
}
 
function findEulerianPathDirected(graph: DirectedGraph): number[] | null {
    const { vertices, adjacencyList } = graph;
    
    // Calculate in-degree and out-degree for each vertex
    const inDegree: number[] = new Array(vertices).fill(0);
    const outDegree: number[] = new Array(vertices).fill(0);
    
    for (let v = 0; v < vertices; v++) {
        outDegree[v] = adjacencyList[v].length;
        for (const neighbor of adjacencyList[v]) {
            inDegree[neighbor]++;
        }
    }
    
    // Find start and end vertices
    let startVertex = -1;
    let endVertex = -1;
    let extraOutgoing = 0;
    let extraIncoming = 0;
    
    for (let v = 0; v < vertices; v++) {
        const diff = outDegree[v] - inDegree[v];
        
        if (diff === 1) {
            extraOutgoing++;
            startVertex = v;
        } else if (diff === -1) {
            extraIncoming++;
            endVertex = v;
        } else if (diff !== 0) {
            return null; // Invalid for Eulerian path
        }
    }
    
    // Validate: either circuit (0 imbalanced) or path (exactly 2 imbalanced)
    if (!(extraOutgoing === 0 && extraIncoming === 0) &&
        !(extraOutgoing === 1 && extraIncoming === 1)) {
        return null;
    }
    
    // For Eulerian circuit, start anywhere; for path, start at startVertex
    const start = startVertex === -1 ? 0 : startVertex;
    
    // Clone adjacency list for modification
    const adj = adjacencyList.map(neighbors => [...neighbors]);
    
    // Hierholzer's algorithm for directed graphs
    const path: number[] = [];
    const stack: number[] = [start];
    
    while (stack.length > 0) {
        const current = stack[stack.length - 1];
        
        if (adj[current].length > 0) {
            const next = adj[current].pop()!;
            stack.push(next);
        } else {
            path.push(stack.pop()!);
        }
    }
    
    path.reverse();
    
    // Verify we used all edges
    const totalEdges = adjacencyList.reduce((sum, n) => sum + n.length, 0);
    if (path.length !== totalEdges + 1) {
        return null; // Graph not connected enough
    }
    
    return path;
}
 
// Example: Simple directed graph with Eulerian path
// 0 → 1 → 2 → 3
// 0 → 2
const directedGraph: DirectedGraph = {
    vertices: 4,
    adjacencyList: [
        [1, 2],  // 0 → 1, 0 → 2
        [2],     // 1 → 2
        [3],     // 2 → 3
        []       // 3 has no outgoing
    ]
};
 
console.log(findEulerianPathDirected(directedGraph));
// Output: [0, 1, 2, 3] or [0, 2, 3] + more edges...
// Actually: [0, 2, 3] misses edge 0→1, 1→2
// Correct path visits all 4 edges: 0→1→2→3 and 0→2
// One valid path: [0, 1, 2, 3] but misses 0→2
// Need to reconsider... The graph has 4 edges.

DNA Sequencing Application

Modern DNA sequencers produce millions of short 'reads' (typically 100-300 base pairs). Finding how these overlap to reconstruct the original genome is essentially an Eulerian path problem on a de Bruijn graph. This application of graph theory revolutionized genomics in the 2000s.

Summary: The Dichotomy of Tractability

The comparison between Eulerian and Hamiltonian problems illustrates one of the deepest themes in computer science: the boundary between tractable and intractable problems.

What Makes Eulerian Problems Tractable:

Local characterization: The condition (even degrees) can be checked at each vertex independently.
No global dependencies: Using an edge at one part of the graph doesn't affect what's possible elsewhere.
Constructive proof: The same reasoning that proves existence also constructs a solution.
Invariant preservation: The algorithm maintains the invariant that remaining edges form a valid structure.

What Makes Hamiltonian Problems Intractable:

Global constraints: Visiting vertex X early may prevent reaching vertex Y later.
Complex dependencies: The effect of a choice propagates throughout the entire graph.
No simple characterization: We can't check existence without essentially searching.
NP-completeness: Any efficient algorithm would solve all NP-complete problems.

Key Takeaways

•Eulerian = Edges, Hamiltonian = Vertices: This seemingly small difference creates a vast complexity gap.
•Euler's theorem provides a complete characterization: Check vertex degrees in O(V + E) to know if an Eulerian path/circuit exists.
•Hierholzer's algorithm finds Eulerian circuits in O(E): Efficient construction is possible once existence is confirmed.
•Hamiltonian is NP-complete: No polynomial-time algorithm is known, and none likely exists.
•Sufficient conditions for Hamiltonicity exist (Dirac, Ore) but are not necessary—many Hamiltonian graphs fail them.
•These problems appear in real applications: DNA sequencing (Eulerian), traveling salesman (Hamiltonian), route optimization, and circuit design.

Looking Ahead:

The contrast between Eulerian and Hamiltonian problems foreshadows our broader study of computational complexity. In the upcoming pages, we'll explore more problems at the boundary of tractability—graph coloring, the Traveling Salesman Problem, and how to recognize when you've encountered an intractable problem in practice.

Understanding this dichotomy is crucial for any engineer. It tells us when to seek efficient algorithms and when to settle for approximations, heuristics, or restricted problem instances.

Page Complete

You now understand the fundamental distinction between Eulerian and Hamiltonian graph traversal problems. You can characterize Eulerian graphs, apply Hierholzer's algorithm, and recognize why Hamiltonian problems resist efficient solution. Next, we'll explore graph coloring—another classical problem with surprising computational depth.

1 / 4

Loading learning content...

Data Structures & AlgorithmsAdvanced Graph Patterns

Advanced Graph Patterns: Classical Problems & Computational Boundaries

LevelAdvanced

Duration90 mins

TopicAdvanced Graph Patterns

1 / 4

Eulerian and Hamiltonian Paths: Two Sides of Graph Traversal

The Two Fundamental Traversal Problems

Graph theory presents two seemingly similar questions that lie at the heart of discrete mathematics and computer science:

Question 1: Can we traverse every edge of a graph exactly once, returning to our starting point?

Question 2: Can we visit every vertex of a graph exactly once, returning to our starting point?

Understanding why these similar-sounding problems have such different complexities provides profound insight into the nature of computation itself.

What You Will Master

Historical Origins: The Königsberg Bridge Problem

The study of Eulerian paths begins with one of the most celebrated problems in the history of mathematics: the Seven Bridges of Königsberg.

The Setting (1736):

Euler's Revolutionary Insight:

Leonhard Euler approached this problem not by attempting various routes, but by abstracting it into what we now call a graph. He represented:

Each landmass (two banks and two islands) as a vertex (node)
Each bridge as an edge connecting two vertices

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
                    Königsberg Graph Representation
               =========================================
               
               The city layout:                     The abstracted graph:
               
                    North Bank                           A (North Bank)
                   /    |    \                          /|\
                 [1]   [2]   [3]                       / | \
                 /      |      \                     e1 e2 e3
                Island C ---- Island D              /   |   \
                   \     [7]    /                  C----e7---D
                   [4]        [5]                   \   |   /
                     \   [6]   /                    e4 e6 e5
                      \   |   /                      \ | /
                     South Bank                        B (South Bank)
               
               Vertices: A (North), B (South), C (Island), D (Island)
               Edges: 7 bridges connecting the landmasses
               
               Degree of each vertex:
               - A (North Bank): 3 bridges → degree 3
               - B (South Bank): 3 bridges → degree 3  
               - C (Island): 3 bridges → degree 3
               - D (Island): 3 bridges → degree 3
               
               All vertices have ODD degree!

Euler's Theorem (1736):

Euler discovered that an Eulerian circuit (a closed walk traversing every edge exactly once) exists if and only if:

The graph is connected (all vertices can reach all others)
Every vertex has even degree

Since all four vertices in the Königsberg graph have odd degree (3), no Eulerian circuit exists. Euler proved this impossible—not by exhaustive search, but by pure logical reasoning.

This 1736 paper is widely considered the birth of both graph theory and topology, making it one of the most important papers in the history of mathematics.

The Power of Abstraction

Formal Definitions: Paths, Circuits, and Trails

Before diving deeper, we need precise definitions. Graph theory terminology can be confusing because different authors use terms differently. Here we establish rigorous definitions:

Basic Walk Terminology:

Walk: A sequence of vertices where consecutive vertices are connected by edges. Vertices and edges may repeat.
Trail: A walk where no edge repeats (but vertices may repeat).
Path: A walk where no vertex repeats (and thus no edge repeats).
Closed Walk/Circuit: A walk that starts and ends at the same vertex.
Cycle: A closed path (no repeated vertices except start = end).

Walk Types and Their Constraints
Type	Edge Repetition	Vertex Repetition	Returns to Start
Walk	Allowed	Allowed	May or may not
Trail	Not allowed	Allowed	May or may not
Path	Not allowed	Not allowed	No
Circuit	Allowed	Allowed	Yes (by definition)
Eulerian Trail	Not allowed (visits each once)	Allowed	No
Eulerian Circuit	Not allowed (visits each once)	Allowed	Yes
Hamiltonian Path	Not allowed	Not allowed (visits each once)	No
Hamiltonian Cycle	Not allowed	Not allowed (visits each once)	Yes

Eulerian Definitions:

Eulerian Trail (Eulerian Path): A trail that visits every edge of the graph exactly once. Does not need to return to the starting vertex.
Eulerian Circuit (Eulerian Cycle): A trail that visits every edge exactly once and returns to the starting vertex. This is a closed Eulerian trail.
Eulerian Graph: A graph that contains an Eulerian circuit.
Semi-Eulerian Graph: A graph that contains an Eulerian trail but not an Eulerian circuit.

Hamiltonian Definitions:

Hamiltonian Path: A path that visits every vertex of the graph exactly once.
Hamiltonian Cycle: A cycle that visits every vertex exactly once and returns to the starting vertex.
Hamiltonian Graph: A graph that contains a Hamiltonian cycle.

Critical Distinction

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
    Consider this graph:
    
         A ------- B
         |\       /|
         | \     / |
         |  \   /  |
         |   \ /   |
         |    X    |
         |   / \   |
         |  /   \  |
         | /     \ |
         |/       \|
         D ------- C
    
    Edges: A-B, A-C, A-D, B-C, B-D, C-D (6 edges = K4, complete graph on 4 vertices)
    
    EULERIAN CIRCUIT (traverse each edge once, return to start):
    --------------------------------------------------------
    A → B → C → D → A → C → B → D → A
    
    Wait, this visits edges: A-B, B-C, C-D, D-A, A-C, C-B, B-D, D-A
    But we have duplicates! Let's try again...
    
    A → B → C → A → D → B → C → D → A  ❌ Still not right
    
    Actually, K4 has 6 edges. Each vertex has degree 3 (odd).
    By Euler's theorem: NO Eulerian circuit exists in K4!
    
    HAMILTONIAN CYCLE (visit each vertex once, return to start):
    -----------------------------------------------------------
    A → B → C → D → A  ✓
    
    This visits each vertex exactly once and returns to start.
    K4 definitely has Hamiltonian cycles!
    
    KEY INSIGHT: A graph can have Hamiltonian cycles without Eulerian circuits!

Euler's Theorems: Complete Characterization

The beauty of Eulerian problems lies in their complete characterization. We can determine whether an Eulerian path or circuit exists by simply counting vertex degrees—no search required.

Theorem 1 (Eulerian Circuit):

A connected graph G has an Eulerian circuit if and only if every vertex has even degree.

Theorem 2 (Eulerian Trail):

Theorem 3 (Impossibility):

If a connected graph has more than two vertices of odd degree, no Eulerian trail or circuit exists.

Why These Theorems Work

•Even Degree Necessity: When we traverse a vertex (neither starting nor ending), we enter via one edge and leave via another. Each traversal 'uses' two edges. For all edges to be used exactly once, we need an even number of edges at each vertex.
•Odd Vertices Must Be Endpoints: At the start vertex, we leave (use one edge) before any entry. At the end vertex, we enter (use one edge) with no exit. These vertices use an odd number of edges. All other vertices must use an even number.
•Exactly Two or Zero: Since every edge connects exactly two vertices, the sum of all degrees equals 2|E| (even). Thus, the number of odd-degree vertices must be even. Combined with the endpoint argument: either 0 (circuit) or 2 (trail) odd vertices.
•The Handshaking Lemma: The sum of all vertex degrees equals 2 × (number of edges). This fundamental lemma underlies the entire theory.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
interface Graph {
    vertices: number;          // Number of vertices (0 to V-1)
    adjacencyList: number[][]; // adjacencyList[v] = list of neighbors
}
 
enum EulerianType {
    NOT_EULERIAN = "No Eulerian path or circuit exists",
    EULERIAN_PATH = "Eulerian path exists (but not circuit)",
    EULERIAN_CIRCUIT = "Eulerian circuit exists"
}
 
/**
 * Determines if a graph has an Eulerian path, circuit, or neither.
 * Time Complexity: O(V + E) - we traverse the adjacency list once
 * Space Complexity: O(1) - only storing counts
 */
function classifyEulerian(graph: Graph): EulerianType {
    // Step 1: Check connectivity (required for both path and circuit)
    if (!isConnected(graph)) {
        // Exception: isolated vertices (degree 0) don't affect Eulerian properties
        // A more precise check would ignore isolated vertices
        return EulerianType.NOT_EULERIAN;
    }
    
    // Step 2: Count vertices with odd degree
    let oddDegreeCount = 0;
    
    for (let v = 0; v < graph.vertices; v++) {
        const degree = graph.adjacencyList[v].length;
        if (degree % 2 !== 0) {
            oddDegreeCount++;
        }
    }
    
    // Step 3: Apply Euler's theorem
    if (oddDegreeCount === 0) {
        // All vertices have even degree → Eulerian circuit exists
        return EulerianType.EULERIAN_CIRCUIT;
    } else if (oddDegreeCount === 2) {
        // Exactly two vertices have odd degree → Eulerian path exists
        return EulerianType.EULERIAN_PATH;
    } else {
        // More than two odd-degree vertices → impossible
        return EulerianType.NOT_EULERIAN;
    }
}
 
/**
 * Check if graph is connected using DFS
 * Ignores isolated vertices (vertices with degree 0)
 */
function isConnected(graph: Graph): boolean {
    // Find a vertex with non-zero degree to start
    let startVertex = -1;
    let nonIsolatedCount = 0;
    
    for (let v = 0; v < graph.vertices; v++) {
        if (graph.adjacencyList[v].length > 0) {
            nonIsolatedCount++;
            if (startVertex === -1) {
                startVertex = v;
            }
        }
    }
    
    // If no edges exist, trivially "connected" (or empty)
    if (startVertex === -1) {
        return true;
    }
    
    // DFS to count reachable non-isolated vertices
    const visited = new Set<number>();
    const stack = [startVertex];
    
    while (stack.length > 0) {
        const current = stack.pop()!;
        if (visited.has(current)) continue;
        visited.add(current);
        
        for (const neighbor of graph.adjacencyList[current]) {
            if (!visited.has(neighbor)) {
                stack.push(neighbor);
            }
        }
    }
    
    // Check if all non-isolated vertices were reached
    return visited.size === nonIsolatedCount;
}
 
// Example usage with the Königsberg bridge graph
const konigsbergGraph: Graph = {
    vertices: 4,  // A=0 (North), B=1 (South), C=2 (Island1), D=3 (Island2)
    adjacencyList: [
        [2, 2, 3],      // A connects to C (2 bridges) and D (1 bridge)
        [2, 2, 3],      // B connects to C (2 bridges) and D (1 bridge)
        [0, 0, 1, 1, 3], // C connects to A (2), B (2), D (1)
        [0, 1, 2]        // D connects to A (1), B (1), C (1)
    ]
};
 
console.log(classifyEulerian(konigsbergGraph)); 
// Output: "No Eulerian path or circuit exists"
// All 4 vertices have odd degree (3, 3, 5, 3)

The Elegance of Characterization

Hierholzer's Algorithm: Finding Eulerian Circuits

Once we've determined that an Eulerian circuit exists, how do we actually find it? Hierholzer's algorithm (1873) provides an elegant O(E) solution.

The Core Insight:

Repeating this process until all edges are used gives us the complete Eulerian circuit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
/**
 * Hierholzer's Algorithm for finding an Eulerian Circuit
 * 
 * Precondition: Graph must have an Eulerian circuit
 *               (connected, all vertices have even degree)
 * 
 * Time Complexity: O(E) - each edge is visited exactly once
 * Space Complexity: O(E) - for the result path and stack
 */
function findEulerianCircuit(
    numVertices: number,
    edges: [number, number][] // List of edges as [u, v] pairs
): number[] {
    // Build adjacency list with edge indices for efficient removal
    // Using a Map to track remaining edges at each vertex
    const adj: Map<number, number[]>[] = Array.from(
        { length: numVertices },
        () => new Map()
    );
    
    // For undirected graph, each edge appears in both directions
    // We use an index to track which edges have been used
    const edgeUsed: boolean[] = new Array(edges.length).fill(false);
    
    for (let i = 0; i < edges.length; i++) {
        const [u, v] = edges[i];
        // Store edge index at both endpoints
        if (!adj[u].has(v)) adj[u].set(v, []);
        if (!adj[v].has(u)) adj[v].set(u, []);
        adj[u].get(v)!.push(i);
        adj[v].get(u)!.push(i);
    }
    
    const circuit: number[] = [];
    const stack: number[] = [0]; // Start from vertex 0
    
    // Track current position in each vertex's neighbor list
    const pointers: Map<number, number>[] = adj.map(
        neighbors => new Map([...neighbors.keys()].map(k => [k, 0]))
    );
    
    while (stack.length > 0) {
        const current = stack[stack.length - 1];
        
        // Find an unused edge from current vertex
        let foundEdge = false;
        
        for (const [neighbor, edgeIndices] of adj[current]) {
            // Try to find an unused edge to this neighbor
            while (pointers[current].get(neighbor)! < edgeIndices.length) {
                const edgeIdx = edgeIndices[pointers[current].get(neighbor)!];
                pointers[current].set(neighbor, pointers[current].get(neighbor)! + 1);
                
                if (!edgeUsed[edgeIdx]) {
                    edgeUsed[edgeIdx] = true;
                    stack.push(neighbor);
                    foundEdge = true;
                    break;
                }
            }
            if (foundEdge) break;
        }
        
        if (!foundEdge) {
            // No more unused edges from this vertex
            // Add it to the circuit (in reverse order)
            circuit.push(stack.pop()!);
        }
    }
    
    // Circuit is built in reverse
    circuit.reverse();
    return circuit;
}
 
// Simplified version using adjacency list with degree tracking
function findEulerianCircuitSimple(adjacencyList: number[][]): number[] {
    // Clone the adjacency list since we'll modify it
    const adj = adjacencyList.map(neighbors => [...neighbors]);
    
    const circuit: number[] = [];
    const stack: number[] = [0];
    
    while (stack.length > 0) {
        const current = stack[stack.length - 1];
        
        if (adj[current].length > 0) {
            // Take an edge from current to a neighbor
            const next = adj[current].pop()!;
            
            // Remove the reverse edge (for undirected graph)
            const reverseIdx = adj[next].indexOf(current);
            if (reverseIdx !== -1) {
                adj[next].splice(reverseIdx, 1);
            }
            
            stack.push(next);
        } else {
            // No more edges from this vertex
            circuit.push(stack.pop()!);
        }
    }
    
    return circuit.reverse();
}
 
// Example: Find Eulerian circuit in a house-shaped graph
//       0
//      /|\
//     1-+-2
//     | X |
//     |/ \|
//     3---4
 
const houseGraph = [
    [1, 2],           // 0 connects to 1, 2
    [0, 2, 3, 4],     // 1 connects to 0, 2, 3, 4
    [0, 1, 3, 4],     // 2 connects to 0, 1, 3, 4
    [1, 2, 4],        // 3 connects to 1, 2, 4
    [1, 2, 3]         // 4 connects to 1, 2, 3
];
 
// Wait - let's verify: degrees are 2, 4, 4, 3, 3
// Vertices 3 and 4 have odd degree! This has Eulerian PATH, not circuit.
 
// Correct example - add edge between 3 and 4 to make all even:
const eulerianGraph = [
    [1, 2],               // Degree 2 (even)
    [0, 2, 3, 4],         // Degree 4 (even)
    [0, 1, 3, 4],         // Degree 4 (even)
    [1, 2, 4, 4],         // Degree 4 (even) - two edges to 4
    [1, 2, 3, 3]          // Degree 4 (even) - two edges to 3
];
 
console.log(findEulerianCircuitSimple(eulerianGraph));
// Possible output: [0, 1, 3, 4, 3, 2, 4, 1, 2, 0]

Algorithm Walkthrough:

Start anywhere (for a circuit, any vertex works)
Traverse edges greedily, marking each as used
When stuck (no unused edges from current vertex), backtrack and record the vertex
Continue until stack is empty
Reverse the recorded sequence to get the Eulerian circuit

Why This Works:

Handling Eulerian Paths

Hamiltonian Problems: A Fundamentally Different Beast

Now we turn to Hamiltonian paths and cycles—problems that look superficially similar to Eulerian problems but are fundamentally different.

The Hamiltonian Cycle Problem:

Given a graph G, does there exist a cycle that visits every vertex exactly once?

The Stark Contrast with Eulerian Problems:

This isn't just because we haven't been clever enough—it's believed to be fundamentally impossible for polynomial-time algorithms.

Eulerian Problems

•Complete characterization exists (degree parity)
•O(V + E) to determine existence
•O(E) to find the actual path/circuit
•Simple necessary and sufficient conditions
•No search required—just count
•Solved elegantly in 1736 by Euler

Hamiltonian Problems

•No known characterization exists
•NP-complete to determine existence
•Exponential time required in worst case
•Only sufficient conditions (not necessary)
•May require exhaustive search
•Unsolved for polynomial time since defined

Why Is Hamiltonian So Much Harder?

The fundamental difference stems from the global nature of the Hamiltonian constraint versus the local nature of the Eulerian constraint:

Eulerian (local): Each edge must be traversed once. This constraint is satisfied by ensuring local conditions at each vertex (even degree). There's no "interaction" between distant parts of the graph.
Hamiltonian (global): Each vertex must appear exactly once in the path. This creates complex dependencies: visiting vertex A early might block access to vertex B later, even if they're not directly connected. The constraint propagates through the entire graph structure.

No local characterization can capture these global dependencies. The only way to verify is to consider the entire path structure—and there are potentially V! orderings to check.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    Consider finding a Hamiltonian path in a complete graph Kn:
    
    n = 5 vertices:
    - Possible orderings: 5! = 120
    - Easily checkable by computer
    
    n = 10 vertices:
    - Possible orderings: 10! = 3,628,800
    - Still manageable
    
    n = 20 vertices:
    - Possible orderings: 20! ≈ 2.4 × 10^18
    - Would take centuries for brute force
    
    n = 50 vertices:
    - Possible orderings: 50! ≈ 3 × 10^64
    - More than atoms in the observable universe
    
    Contrast with Eulerian:
    - For ANY n, just count degrees: O(n) operations
    - No explosion of possibilities
    
    This is the essence of the P vs NP distinction.

Sufficient Conditions for Hamiltonian Cycles

Theorem (Dirac, 1952):

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

Theorem (Ore, 1960):

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

Special Cases:

Complete graphs Kn (n ≥ 3): Always Hamiltonian
Complete bipartite graphs Km,n (m = n): Always Hamiltonian
Hypercubes Qn: Always Hamiltonian for n ≥ 2

Sufficient ≠ Necessary

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
/**
 * Backtracking algorithm to find a Hamiltonian cycle
 * 
 * Time Complexity: O(n!) worst case - exponential
 * Space Complexity: O(n) for the path and recursion stack
 * 
 * This demonstrates the computational difficulty of Hamiltonian problems.
 */
function findHamiltonianCycle(adjacencyList: number[][]): number[] | null {
    const n = adjacencyList.length;
    if (n < 3) return null; // Need at least 3 vertices for a cycle
    
    const path: number[] = new Array(n).fill(-1);
    const visited: boolean[] = new Array(n).fill(false);
    
    // Start from vertex 0
    path[0] = 0;
    visited[0] = true;
    
    function backtrack(pos: number): boolean {
        // Base case: all vertices are in the path
        if (pos === n) {
            // Check if there's an edge from last vertex back to first
            const lastVertex = path[n - 1];
            const firstVertex = path[0];
            return adjacencyList[lastVertex].includes(firstVertex);
        }
        
        // Try each vertex as the next in the path
        for (const nextVertex of adjacencyList[path[pos - 1]]) {
            if (!visited[nextVertex]) {
                // Choose
                path[pos] = nextVertex;
                visited[nextVertex] = true;
                
                // Explore
                if (backtrack(pos + 1)) {
                    return true;
                }
                
                // Unchoose (backtrack)
                visited[nextVertex] = false;
                path[pos] = -1;
            }
        }
        
        return false;
    }
    
    if (backtrack(1)) {
        return path;
    }
    return null;
}
 
// Optimized version with pruning
function findHamiltonianCycleOptimized(adjacencyList: number[][]): number[] | null {
    const n = adjacencyList.length;
    if (n < 3) return null;
    
    // Precompute for pruning: if any vertex becomes unreachable, abort
    const path: number[] = [0];
    const visited: boolean[] = new Array(n).fill(false);
    visited[0] = true;
    
    function canComplete(path: number[]): boolean {
        // Early pruning: check if remaining vertices are still reachable
        const remaining = n - path.length;
        if (remaining === 0) return true;
        
        // Check if every unvisited vertex has at least one unvisited neighbor
        // (or is connected to path endpoint)
        for (let v = 0; v < n; v++) {
            if (!visited[v]) {
                let hasConnection = false;
                for (const neighbor of adjacencyList[v]) {
                    if (!visited[neighbor] || neighbor === path[path.length - 1]) {
                        hasConnection = true;
                        break;
                    }
                }
                if (!hasConnection && remaining > 1) return false;
            }
        }
        return true;
    }
    
    function backtrack(): boolean {
        if (path.length === n) {
            return adjacencyList[path[n - 1]].includes(0);
        }
        
        const current = path[path.length - 1];
        
        // Sort neighbors by degree (choose most constrained first - heuristic)
        const neighbors = [...adjacencyList[current]]
            .filter(v => !visited[v])
            .sort((a, b) => {
                const degA = adjacencyList[a].filter(x => !visited[x]).length;
                const degB = adjacencyList[b].filter(x => !visited[x]).length;
                return degA - degB; // Most constrained first
            });
        
        for (const next of neighbors) {
            path.push(next);
            visited[next] = true;
            
            if (canComplete(path) && backtrack()) {
                return true;
            }
            
            visited[next] = false;
            path.pop();
        }
        
        return false;
    }
    
    if (backtrack()) {
        return path;
    }
    return null;
}
 
// Example: Pentagon graph (cycle of 5)
const pentagon = [
    [1, 4],  // 0
    [0, 2],  // 1
    [1, 3],  // 2
    [2, 4],  // 3
    [3, 0]   // 4
];
 
console.log(findHamiltonianCycle(pentagon)); 
// Output: [0, 1, 2, 3, 4] - trivially Hamiltonian since it's a cycle

Directed Graphs and Variations

Both Eulerian and Hamiltonian concepts extend to directed graphs with modified conditions.

Eulerian Circuits in Directed Graphs:

A strongly connected directed graph has an Eulerian circuit if and only if:

Every vertex has in-degree equal to out-degree

For an Eulerian path (not circuit):

At most one vertex has out-degree = in-degree + 1 (start vertex)
At most one vertex has in-degree = out-degree + 1 (end vertex)
All other vertices have in-degree = out-degree

Common Applications:

Real-World Applications of Eulerian and Hamiltonian Concepts
Problem	Graph Type	Concept	Application
DNA Fragment Assembly	Directed	Eulerian Path	De Bruijn graphs for genome sequencing
Chinese Postman Problem	Undirected/Directed	Eulerian Path	Minimum-distance route covering all streets
Traveling Salesman	Complete + Weights	Hamiltonian Cycle	Minimum-cost tour visiting all cities
Knight's Tour	Undirected	Hamiltonian Path	Chess knight visiting all squares once
Circuit Board Testing	Directed	Eulerian Path	Testing all connections with one probe run
Gray Code Generation	Hypercube	Hamiltonian Cycle	Binary counting with single-bit changes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/**
 * Find Eulerian path in directed graph
 * Used in DNA fragment assembly via de Bruijn graphs
 * 
 * The de Bruijn graph approach:
 * 1. Break DNA reads into k-mers (length k substrings)
 * 2. Create vertices for (k-1)-mers
 * 3. Create edges for k-mers connecting their prefix to suffix
 * 4. Find Eulerian path to reconstruct the original sequence
 */
interface DirectedGraph {
    vertices: number;
    adjacencyList: number[][];  // outgoing edges only
}
 
function findEulerianPathDirected(graph: DirectedGraph): number[] | null {
    const { vertices, adjacencyList } = graph;
    
    // Calculate in-degree and out-degree for each vertex
    const inDegree: number[] = new Array(vertices).fill(0);
    const outDegree: number[] = new Array(vertices).fill(0);
    
    for (let v = 0; v < vertices; v++) {
        outDegree[v] = adjacencyList[v].length;
        for (const neighbor of adjacencyList[v]) {
            inDegree[neighbor]++;
        }
    }
    
    // Find start and end vertices
    let startVertex = -1;
    let endVertex = -1;
    let extraOutgoing = 0;
    let extraIncoming = 0;
    
    for (let v = 0; v < vertices; v++) {
        const diff = outDegree[v] - inDegree[v];
        
        if (diff === 1) {
            extraOutgoing++;
            startVertex = v;
        } else if (diff === -1) {
            extraIncoming++;
            endVertex = v;
        } else if (diff !== 0) {
            return null; // Invalid for Eulerian path
        }
    }
    
    // Validate: either circuit (0 imbalanced) or path (exactly 2 imbalanced)
    if (!(extraOutgoing === 0 && extraIncoming === 0) &&
        !(extraOutgoing === 1 && extraIncoming === 1)) {
        return null;
    }
    
    // For Eulerian circuit, start anywhere; for path, start at startVertex
    const start = startVertex === -1 ? 0 : startVertex;
    
    // Clone adjacency list for modification
    const adj = adjacencyList.map(neighbors => [...neighbors]);
    
    // Hierholzer's algorithm for directed graphs
    const path: number[] = [];
    const stack: number[] = [start];
    
    while (stack.length > 0) {
        const current = stack[stack.length - 1];
        
        if (adj[current].length > 0) {
            const next = adj[current].pop()!;
            stack.push(next);
        } else {
            path.push(stack.pop()!);
        }
    }
    
    path.reverse();
    
    // Verify we used all edges
    const totalEdges = adjacencyList.reduce((sum, n) => sum + n.length, 0);
    if (path.length !== totalEdges + 1) {
        return null; // Graph not connected enough
    }
    
    return path;
}
 
// Example: Simple directed graph with Eulerian path
// 0 → 1 → 2 → 3
// 0 → 2
const directedGraph: DirectedGraph = {
    vertices: 4,
    adjacencyList: [
        [1, 2],  // 0 → 1, 0 → 2
        [2],     // 1 → 2
        [3],     // 2 → 3
        []       // 3 has no outgoing
    ]
};
 
console.log(findEulerianPathDirected(directedGraph));
// Output: [0, 1, 2, 3] or [0, 2, 3] + more edges...
// Actually: [0, 2, 3] misses edge 0→1, 1→2
// Correct path visits all 4 edges: 0→1→2→3 and 0→2
// One valid path: [0, 1, 2, 3] but misses 0→2
// Need to reconsider... The graph has 4 edges.

DNA Sequencing Application

Summary: The Dichotomy of Tractability

The comparison between Eulerian and Hamiltonian problems illustrates one of the deepest themes in computer science: the boundary between tractable and intractable problems.

What Makes Eulerian Problems Tractable:

Local characterization: The condition (even degrees) can be checked at each vertex independently.
No global dependencies: Using an edge at one part of the graph doesn't affect what's possible elsewhere.
Constructive proof: The same reasoning that proves existence also constructs a solution.
Invariant preservation: The algorithm maintains the invariant that remaining edges form a valid structure.

What Makes Hamiltonian Problems Intractable:

Global constraints: Visiting vertex X early may prevent reaching vertex Y later.
Complex dependencies: The effect of a choice propagates throughout the entire graph.
No simple characterization: We can't check existence without essentially searching.
NP-completeness: Any efficient algorithm would solve all NP-complete problems.

Key Takeaways

•Eulerian = Edges, Hamiltonian = Vertices: This seemingly small difference creates a vast complexity gap.
•Euler's theorem provides a complete characterization: Check vertex degrees in O(V + E) to know if an Eulerian path/circuit exists.
•Hierholzer's algorithm finds Eulerian circuits in O(E): Efficient construction is possible once existence is confirmed.
•Hamiltonian is NP-complete: No polynomial-time algorithm is known, and none likely exists.
•Sufficient conditions for Hamiltonicity exist (Dirac, Ore) but are not necessary—many Hamiltonian graphs fail them.
•These problems appear in real applications: DNA sequencing (Eulerian), traveling salesman (Hamiltonian), route optimization, and circuit design.

Looking Ahead:

Understanding this dichotomy is crucial for any engineer. It tells us when to seek efficient algorithms and when to settle for approximations, heuristics, or restricted problem instances.

Page Complete

1 / 4