Eulerian & Hamiltonian

Knowledge Map Atlas
Eulerian Hamiltonian Representations Verifying a Hamiltonian Cycle (Coding)

Eulerian

Building on the graph theory foundations, three traversal questions about a graph illustrate strikingly different computational landscapes:

PATH is solved in polynomial time by breadth-first search. Eulerian admits, for connected graphs, a degree-parity test (Euler's theorem below). Hamiltonian, despite its surface similarity to Eulerian, is NP-complete. The remainder of this page develops the contrast between the latter two. PATH reappears when we study walks on graphs and network flow. The notion of polynomial time used here is formalized in our study of time complexity.

The Eulerian concept originates from Leonhard Euler's 1736 analysis of the Seven Bridges of Königsberg, widely considered the birth of graph theory. We adopt the strict simple-graph setting from the graph definition. The original Königsberg problem involves a multigraph (parallel bridges between landmasses), which lies outside this setting. Collapsing the parallel edges would not help, because it changes the vertex degrees and hence the answer.

Convention. Throughout this page we use three operational notions of traversal. A walk in \(G\) is a sequence of vertices \(v_0, v_1, \ldots, v_k\) with each consecutive pair \(v_{i-1} v_i\) an edge of \(G\). Vertices and edges may repeat. A trail is a walk in which no edge repeats (vertices may still repeat). A walk or trail is closed if \(v_0 = v_k\). These notions receive a formal definition in walks and trails. The operational descriptions above suffice here.

Definition: Eulerian and Semi-Eulerian Graphs

A graph is Eulerian if it contains an Eulerian cycle (also called an Euler tour). An Eulerian cycle is a closed walk that traverses every edge exactly once. (Vertices may be revisited. Only the no-edge-repetition constraint is required, so an Eulerian cycle is in fact a closed trail covering all of \(E\).)

A graph is semi-Eulerian if it contains an Eulerian path (also called an Eulerian trail) with two distinct endpoints. Such a path is a trail that traverses every edge exactly once but does not close up. By this convention, the Eulerian and semi-Eulerian classes are disjoint.

Theorem: Euler's Characterization of Eulerian Graphs (1736)

A connected graph is Eulerian if and only if every vertex has even degree.

Examples of Eulerian and semi-Eulerian graphs

These small cases match the theorem's degree-parity criterion and exhibit three kinds of behavior: Eulerian, semi-Eulerian, and Eulerian with a revisited vertex. Having checked the theorem on examples, we now prove it in general.

The forward direction below is a local pairing argument at each vertex of the cycle, in the same double-counting spirit as the handshaking lemma. The converse is constructive and produces an explicit algorithm. This argument is due to Carl Hierholzer (1873), who showed that the procedure of greedily extending a closed trail and then splicing in further closed sub-trails terminates with an Eulerian cycle. Euler himself proved only the necessity direction in 1736, and a proof of sufficiency waited 137 years. We present Hierholzer's argument in self-contained form.

Proof.

(\(\Rightarrow\)) Suppose \(G\) admits an Eulerian cycle \(C\). Fix any vertex \(v\). Each visit to \(v\) along \(C\) consists of one entering edge paired with one leaving edge, and every edge incident to \(v\) appears in exactly one such pair (by the "every edge exactly once" property). Hence the edges incident to \(v\) split into pairs, so \(\deg(v)\) is even.

(\(\Leftarrow\)) Suppose \(G\) is connected and every vertex has even degree.

Boundary case. If \(|E| = 0\), then \(G\) consists of isolated vertices. Connectivity forces \(|V| = 1\), and the trivial walk at the single vertex (length 0) is vacuously an Eulerian cycle. Assume henceforth \(|E| \geq 1\), so by even-degree some vertex has degree \(\geq 2\).

Step 1 (closed trail at a chosen base vertex). Pick any vertex \(v_0\) with \(\deg(v_0) \geq 2\). Build a trail greedily. At each step, if the current endpoint has an unused incident edge, extend the trail along one such edge. The procedure must terminate because \(|E|\) is finite. We claim the trail terminates at \(v_0\).

Indeed, fix any intermediate vertex \(v \neq v_0\). Each full visit to \(v\) (entering and then leaving) uses exactly two incident edges of \(v\), so between visits an even number of them have been used. Immediately after entering \(v\) without yet leaving, the count is odd. Hence at any moment when the trail has just entered \(v\), an odd number of \(v\)-incident edges have been used. Since \(\deg(v)\) is even, at least one unused incident edge remains, and the trail can be extended. The trail therefore cannot terminate at any \(v \neq v_0\), so it closes at \(v_0\). Call this closed trail \(C\).

Step 2 (residual subgraph still has even degrees). Let \(G' = (V, E \setminus E(C))\) be the subgraph obtained by removing the edges of \(C\). For each \(v \in V(C)\), the closed trail \(C\) uses an even number of incident edges at \(v\) (each visit pairs an entry with an exit), so \(\deg_{G'}(v) = \deg_G(v) - (\text{even})\) remains even. Vertices outside \(V(C)\) have unchanged even degree.

Step 3 (existence of a splice point). If \(E(C) = E\), then \(C\) is the desired Eulerian cycle and we are done. Otherwise \(G'\) has at least one edge. Suppose for contradiction that no vertex of \(C\) has positive \(G'\)-degree. Then every \(G'\)-edge lies entirely in \(V(G) \setminus V(C)\). On the other hand, every edge of \(C\) has both endpoints in \(V(C)\) by the very definition of \(V(C)\) as the vertex set of \(C\). Since \(E(G) = E(G') \sqcup E(C)\), no edge of \(G\) connects \(V(C)\) to \(V(G) \setminus V(C)\). The existence of a \(G'\)-edge implies \(V(G) \setminus V(C) \neq \emptyset\), so no path in \(G\) joins a vertex of \(V(C)\) to a vertex of \(V(G) \setminus V(C)\), since such a path would have to use an edge between the two sets. This contradicts the fact that \(G\) is connected.

Hence some \(u \in V(C)\) satisfies \(\deg_{G'}(u) \geq 1\). Since \(\deg_{G'}(u)\) is even and positive, we have \(\deg_{G'}(u) \geq 2\). Apply Step 1 inside \(G'\) starting at \(u\) to obtain a closed trail \(C'\) in \(G'\) of length at least 2.

Step 4 (splice). The vertex \(u\) appears at least once on \(C\). We fix one such occurrence. Form a new closed walk by traversing \(C\) up to that occurrence of \(u\), then traversing all of \(C'\) (which begins and ends at \(u\)), then continuing along the remainder of \(C\). The result is a closed walk in \(G\) using exactly \(E(C) \cup E(C')\), a disjoint union (\(E(C')\) lies in \(G'\)), so no edge is repeated. The spliced walk is therefore a closed trail strictly longer than \(C\).

Termination. Replace \(C\) by the spliced trail and return to Step 2. Each iteration strictly increases the edge count of \(C\) by at least 2, and \(|E|\) is finite, so the procedure halts after finitely many iterations with \(E(C) = E\). At that point \(C\) is an Eulerian cycle.

Hamiltonian

Definition: Hamiltonian Graph

A graph \(G\) on \(n \geq 3\) vertices is Hamiltonian if it contains a Hamiltonian cycle. A Hamiltonian cycle is a spanning subgraph isomorphic to the cycle \(C_n\). Equivalently, it is a closed walk \(v_0 \to v_1 \to \cdots \to v_{n-1} \to v_0\) in \(G\) in which all \(v_0, v_1, \ldots, v_{n-1}\) are distinct (the closing return to \(v_0\) is the only repetition).

Whereas an Eulerian cycle is a closed trail spanning all of \(E(G)\) and need not be a cycle in the graph-theoretic sense, a Hamiltonian cycle is a graph-theoretic cycle and spans \(V(G)\). One notion spans the edges, the other the vertices.

Graph 1 (the 4-cycle \(C_4\)) is both Eulerian and Hamiltonian. Graph 3 consists of the triangles \(\triangle ABC\) and \(\triangle ADE\) sharing the vertex \(A\). It is Eulerian (all degrees even) but not Hamiltonian. Indeed, deleting \(A\) from a Hamiltonian cycle would leave a path through \(B, C, D, E\). No such path exists, because once \(A\) is removed the only edges left are \(BC\) and \(DE\).

Conversely, Graph 4 below is Hamiltonian but not Eulerian. It has six vertices of odd degree (\(F, G, H, I, J\) of degree 3 and \(K\) of degree 5), violating the even-degree condition. Neither notion therefore implies the other.

Graph 4: Hamiltonian but not Eulerian

For example, the cycle \(A \to G \to C \to I \to K \to H \to B \to F \to E \to D \to J \to A\) is Hamiltonian. The coding section below verifies this computationally.

By Euler's characterization above, determining whether a connected graph is Eulerian reduces to checking that every vertex has even degree. A single pass over the edges computes all degrees in \(O(n + m)\) time, where \(n = |V|\) and \(m = |E|\), which places the problem firmly in class P. In stark contrast, deciding whether a graph is Hamiltonian is NP-complete, a classical result that we state without proof. No polynomial-time algorithm is known, and no efficient combinatorial characterization analogous to the degree condition is known either.

However, a proposed Hamiltonian cycle is easy to verify in polynomial time. We simply check that the graph has at least three vertices, that the proposed cycle 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 the theory of computation formalizes through the class NP.

Graph Representations

A polynomial-time verifier for the Hamiltonian-cycle problem can be implemented in only a few lines of code. Doing so, however, first requires fixing how a graph is stored inside a computer. The choice of representation directly governs the time and space cost of every algorithm acting on the graph, including the verifier we will write below.

Definition: Adjacency Matrix

The adjacency matrix of a graph whose \(n\) vertices are listed in a fixed order is the \(n \times n\) matrix \(\boldsymbol{A}\) whose \((i,j)\)-entry is \(1\) if the \(i\)-th and \(j\)-th vertices are adjacent, and \(0\) otherwise. For undirected graphs, \(\boldsymbol{A}\) is symmetric. The representation requires \(O(n^2)\) space.

Definition: Adjacency List

The adjacency list representation stores, for each vertex, a list of its neighbors. For a graph with \(n\) vertices and \(m = |E|\) edges, it requires \(O(n + m)\) space.

For instance, Graph 4 has the following adjacency matrix (vertices labeled \(A, B, \ldots, K\) correspond to row/column indices \(0, 1, \ldots, 10\)): \[ \boldsymbol{A} = \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} \] The first row, for example, lists the connections of vertex \(A\) (row 0). Its entries are \(1\) at columns \(B, E, G, J\) and \(0\) elsewhere. In particular, the diagonal entry \(\boldsymbol{A}_{00}\) is \(0\), since the graph definition admits no self-loops. Symmetry of \(\boldsymbol{A}\) reflects the undirected nature of the graph.

The choice between matrix and list is not merely cosmetic. A real computer does not have infinite memory, and for graphs with large \(n\) the \(O(n^2)\) cost of the matrix becomes prohibitive. The problem is especially acute because most real-world graphs (social networks, road networks, citation graphs) are sparse, with \(m\) growing far slower than \(n^2\). The adjacency list reduces storage from \(O(n^2)\) to \(O(n + m)\), often by orders of magnitude. On the other hand, the matrix offers \(O(1)\) edge-existence queries (just look at \(\boldsymbol{A}_{ij}\)), whereas the list requires scanning the neighbor list of one endpoint. (The code below stores each neighbor list as a Python set, which brings the expected query cost back to \(O(1)\).)

Verifying a Hamiltonian Cycle

To make the contrast between Eulerian and Hamiltonian concrete, we now implement the verification side of the Hamiltonian problem. Given a candidate cycle, we decide in polynomial time whether it is a Hamiltonian cycle of the graph. This polynomial-time verifier is what places the Hamiltonian problem inside NP. 

      
                                # Matrix version: O(1) edge lookup, O(n^2) space.
                                # Shown here for comparison with the list version below; not invoked in main.
                                def is_hamiltonian_cycle(adj_matrix, cycle):
                                    n = len(adj_matrix)  # get number of vertices
                                    # A Hamiltonian cycle needs at least three vertices; it must visit all vertices and return to start
                                    if n < 3 or 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
                                    if set(cycle[:n]) != set(range(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 s and t
                                            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

                                # Adjacency-list version (used in the demo below)
                                def is_hamiltonian_cycle_list(adj_list, cycle):
                                    n = len(adj_list)  # number of vertices
                                    
                                    if n < 3 or len(cycle) != n + 1:
                                        return False
                                    
                                    if cycle[0] != cycle[n]:
                                        return False
                                    
                                    if set(cycle[:n]) != set(range(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 Eulerian and Hamiltonian problems show how superficially similar graph-theoretic questions can, unless \(P = NP\), have fundamentally different computational complexities. This gap motivates the formal study of NP-completeness, where we classify problems by their inherent computational difficulty.