Eulerian & Hamiltonian

Eulerian

Building on the graph theory foundations, we now study two classical problems about traversing a graph: Can we traverse every edge exactly once? Can we visit every vertex exactly once? These seemingly similar questions turn out to have vastly different computational complexities - a theme that connects directly to the theory of computation.

A graph is called Eulerian if it contains an Eulerian cycle (also called an Euler tour) - a closed walk that traverses every edge exactly once, though vertices may be revisited. This concept originates from Leonhard Euler's groundbreaking work on the Seven Bridges of Königsberg (1736), which is widely considered the birth of graph theory.

The PATH problem asks whether a directed path exists from vertex \(s\) to vertex \(t\). In this section, we explore key path-related concepts that bridge computer science and mathematics.

A graph is called Eulerian if it contains an Eulerian cycle (Euler tour) - a closed walk that traverses every edge exactly once allowing for revisiting vertices. This idea originates from Leonhard Euler's groundbreaking work on the Seven Bridges of Königsberg, which laid the foundations of graph theory.

• Graph 1 is Eulerian since every vertex has degree 2.
• Graph 2 is semi-Eulerian since it has an Eulerian path but not an Eulerian cycle.
• Graph 3 is Eulerian since vertex \(A\) has degree 4 and all other vertices have degree 2.

In Graph 3, vertex \(A\) must be revisited in any Eulerian cycle. In Graph 1, no vertex is revisited (except the starting vertex, which is visited twice to close the cycle). This distinction highlights that an Eulerian cycle is a closed walk, not necessarily a cycle in the graph-theoretic sense.

Hamiltonian

Graph 1 is both Eulerian and Hamiltonian. Graph 3 is Eulerian but not Hamiltonian (vertex \(A\) would need to appear twice in any traversal of all edges). Since a Hamiltonian cycle concerns only vertices, not all edges need be used — so being Hamiltonian does not imply being Eulerian, and vice versa. The following Graph 4 is Hamiltonian but not Eulerian.

(For instance, there is a Hamiltonian cycle: \(A \to G \to C \to I \to K \to H \to B \to F \to E \to D \to J \to A\).)

By Euler's Theorem, determining whether a given graph is Eulerian reduces to checking that every vertex has even degree - an \(O(n)\) computation, placing the problem firmly in class P. In stark contrast, deciding whether a graph is Hamiltonian is NP-complete: no polynomial-time algorithm is known, and no efficient characterization analogous to Euler's degree condition exists.

However, if someone presents a proposed Hamiltonian cycle, it is easy to verify it in polynomial time - simply check that it visits each vertex exactly once and that each consecutive pair is connected by an edge. This distinction between the difficulty of finding a solution and verifying a given solution is precisely the idea behind polynomial verifiability, which we formalize in the next page on the computation track.

Is Hamiltonian Cycle?

Let's make an adjacency matrix for Graph 4: \[ G_4 = \begin{bmatrix} 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \end{bmatrix} \] In the adjacency matrix, the \((i, j)\)-entry is 1 if there is an edge between vertex \(i\) and vertex \(j\), and 0 otherwise. For example, the first row represents the connections of vertex \(A\) to all vertices (including itself).

So far, we have discussed only time complexity, in other words, the "performance" for certain operations. However, a real computer does not have infinite memory. Space complexity matters. For large \(n\), it costs too much memory space, and most real-world graphs are indeed, sparse.

      
                                # Check if a given cycle in the graph is Hamiltonian cycle or not : O(n)
                                # Here, we don't run this function. 
                                def is_hamiltonian_cycle(adj_matrix, cycle):
                                    n = len(adj_matrix)  # get number of vertices
                                    # Check cycle length: must visit all vertices and return to start
                                    if len(cycle) != n + 1:
                                        return False
                                    # Check starts and ends at the same vertex
                                    if cycle[0] != cycle[n]: 
                                        return False
                                    # Check all vertices (except last) are unique and cover all vertices
                                    visited = set(cycle[:n])
                                    if len(visited) != n:
                                        return False
                                    # Check edges between consecutive vertices
                                    for i in range(n):
                                        s, t = cycle[i], cycle[i + 1]
                                        if adj_matrix[s][t] == 0:  # No edge between u and v
                                            return False
                                    return True

                                # Convert adjacency matrix to adjacency List
                                def matrix_to_adj_list(adj_matrix):
                                    adj_list = {}
                                    n = len(adj_matrix)
                                    for i in range(n):
                                        adj_list[i] = set()
                                        for j in range(n):
                                            if adj_matrix[i][j] == 1:
                                                adj_list[i].add(j)
                                    return adj_list

                                # for adjacency List (We use this one!)
                                def is_hamiltonian_cycle_list(adj_list, cycle):
                                    n = len(adj_list)  # number of vertices
                                    
                                    if len(cycle) != n + 1:
                                        return False
                                    
                                    if cycle[0] != cycle[n]:
                                        return False
                                    visited = set(cycle[:n])
                                    
                                    if len(visited) != n:
                                        return False
                                    
                                    for i in range(n):
                                        s, t = cycle[i], cycle[i + 1]
                                        if t not in adj_list[s]:
                                            return False
                                        
                                    return True

                                # Convert the vertex numbers (0, 1, ...,) to letters (A, B, ...,) 
                                def print_adj_list(adj_list):
                                    print("Adjacency List: ")
                                    for v in adj_list:
                                        v_char = chr(ord('A') + v)
                                        neighbors = [chr(ord('A') + u) for u in adj_list[v]]
                                        neighbors_str = ', '.join(sorted(neighbors))
                                        print(f"{v_char}: {neighbors_str}")
                                    print()  
                                        
                                # Print cycle and its result
                                def print_cycle_with_result(cycle, adj_list):
                                    cycle_letters = [chr(ord('A') + v) for v in cycle]
                                    print("Cycle: ", " → ".join(cycle_letters))
                                    is_hamiltonian = is_hamiltonian_cycle_list(adj_list, cycle)
                                    print("Is this Hamiltonian?:", is_hamiltonian)
                                    print() 

                                if __name__ == "__main__":
                                    # Example: Graph 4
                                    G_4 = [
                                    [0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0],  # Vertex A
                                    [1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0],  # Vertex B
                                    [0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0],  # Vertex C
                                    [0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0],  # Vertex D
                                    [1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0],  # Vertex E
                                    [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1],  # Vertex F
                                    [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],  # Vertex G
                                    [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],  # Vertex H
                                    [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1],  # Vertex I
                                    [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],  # Vertex J
                                    [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0],  # Vertex K
                                    ]

                                    # Use the  adjacency List 
                                    adj_list_4 = matrix_to_adj_list(G_4)
                                    print_adj_list(adj_list_4)
                                    
                                    # Valid Hamiltonian cycle
                                    cycle1 = [0, 6, 2, 8, 10, 7, 1, 5, 4, 3, 9, 0]
                                    print_cycle_with_result(cycle1, adj_list_4)

                                    # Invalid cycle
                                    cycle2 = [0, 1, 2, 3, 4, 5, 7, 6, 10, 9, 8, 0]
                                    print_cycle_with_result(cycle2, adj_list_4)
                            

The contrast between Eulerian and Hamiltonian problems is a striking example of how superficially similar graph-theoretic questions can have fundamentally different computational complexities. Euler's Theorem gives a complete, efficiently checkable characterization for Eulerian graphs, while no analogous characterization is known for Hamiltonian graphs. This motivates the formal study of NP-completeness, where we classify problems by their inherent computational difficulty.