Eulerian & Hamiltonian

Eulerian Hamiltonian Representations Is 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 an even simpler 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 complexity-theoretic vocabulary used here is formalized in the theory of computation track.

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 our framework accommodates by collapsing parallel edges and tracking multiplicities separately.

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\). A formal owner block for these notions will be developed in network flow; the operational descriptions above suffice for the present chapter.

Definition: Eulerian and Semi-Eulerian Graphs

A graph is Eulerian if it contains an Eulerian cycle (also called an Euler tour) — 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 — a trail that traverses every edge exactly once but does not close up. By this convention, an Eulerian graph is not also semi-Eulerian: the two 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 three small cases match the theorem's degree-parity criterion and exhibit the full range of behaviour: Eulerian, semi-Eulerian, and Eulerian-with-revisits. They confirm the theorem on examples; we now prove it in general.

The forward direction below uses a local pairing argument that is essentially the handshaking lemma applied at each vertex of the cycle. The converse is genuinely constructive: it produces an explicit algorithm. The constructive 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; the constructive 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\). After every full visit to \(v\) (entering and then leaving), exactly two incident edges of \(v\) 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. Termination is therefore impossible at any \(v \neq v_0\), forcing the trail to close 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 \(V(C)\) and \(V(G) \setminus V(C)\) form a non-trivial disconnection of \(G\) — contradicting connectivity. Hence some \(u \in V(C)\) satisfies \(\deg_{G'}(u) \geq 1\); since \(\deg_{G'}(u)\) is even and positive, in fact \(\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\); fix any 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 result 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\) — an Eulerian cycle. \(\blacksquare\)

Hamiltonian

Definition: Hamiltonian Graph

A graph \(G\) on \(n\) vertices is Hamiltonian if it contains a Hamiltonian cycle — a spanning subgraph isomorphic to the cycle \(C_n\). Equivalently, 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)\). The two notions are dual: edge-spanning vs. vertex-spanning.

Graph 1 (the 4-cycle \(C_4\)) is both Eulerian and Hamiltonian. Graph 3 — two triangles \(\triangle ABC\) and \(\triangle ADE\) sharing the vertex \(A\) — is Eulerian (all degrees even) but not Hamiltonian: a Hamiltonian cycle would visit \(A\) exactly once, but \(A\) is a cut vertex (removing \(A\) disconnects the two triangles), so no single cycle through \(A\) can span all five vertices. 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. The two notions are therefore independent — neither 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 given graph is Eulerian reduces to checking that every vertex has even degree — an \(O(n)\) computation that follows the parity bookkeeping of the handshaking lemma, 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 combinatorial characterization analogous to the 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 the computation track 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 — but doing so 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 with \(n\) vertices is the \(n \times n\) matrix \(\boldsymbol{A}\) whose \((i,j)\)-entry is \(1\) if vertices \(i\) and \(j\) 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 — much more efficient for sparse graphs where \(m \ll n^2\).

For instance, Graph 4 has the following adjacency matrix (vertices labeled \(A, B, \ldots, K\) correspond to row/column indices \(0, 1, \ldots, 10\)): \[ 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} \] The first row, for example, lists the connections of vertex \(A\) (= row 0): the entries are \(1\) at columns \(B, E, G, J\) and \(0\) elsewhere, including the diagonal entry \(A A\) — Graph 4 has no self-loops, in keeping with the simple-graph graph definition. 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 — especially since 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 trade-off is intrinsic, not technical.

Is 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, decide in polynomial time whether it is a Hamiltonian cycle of the graph. This is the polynomial-time verifier that 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
                                    # 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 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 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 characterization gives a complete, efficiently checkable test for Eulerian graphs (degree parity), while no analogous combinatorial characterization is known for Hamiltonian graphs. This motivates the formal study of NP-completeness, where we classify problems by their inherent computational difficulty.