Can you draw a figure without lifting your pen and without retracing a line? Can a postman walk every street exactly once and return to the post office? Can a salesman visit every city exactly once and come home? The first two questions are about using every edge once; the third is about visiting every vertex once. They sound alike, but they could hardly be more different. The edge version has a simple, complete answer: Euler stated it in 1736, and Carl Hierholzer published the full proof in 1873. The vertex version is NP-complete, and nobody knows an efficient algorithm for it.
This chapter covers both: Euler paths and circuits (with a full proof of Euler's theorem and Hierholzer's algorithm), and Hamiltonian paths and cycles (with Dirac's and Ore's sufficient conditions, useful necessary conditions, and the famous Petersen graph). It uses degrees, connectivity and bipartite graphs from Graph Theory Basics.
An Euler circuit in a graph G is a closed trail that uses every edge of G exactly once. An Euler path (Euler trail) is a trail that uses every edge exactly once. A Hamiltonian cycle is a cycle that visits every vertex exactly once; a Hamiltonian path is a path that visits every vertex exactly once.
The Bridges of Königsberg
The city of Königsberg (now Kaliningrad) had four land areas joined by seven bridges. Citizens wondered whether they could take a walk crossing every bridge exactly once. Euler turned the map into a multigraph: one vertex per land area, one edge per bridge.
B (north bank)
║ ╲
║ ╲
A ─── D A = island (Kneiphof), D = land to the east
║ ╱ ║ = two parallel bridges
║ ╱
C (south bank)
Edges: A–B, A–B, A–C, A–C, A–D, B–D, C–D
Degrees: A = 5, B = 3, C = 3, D = 3
Euler's key observation (he proved this necessary condition; the converse was proved later): every time a walk passes through a land area, it uses one bridge to arrive and another to leave. So every vertex except the start and end of the walk must have even degree. Königsberg has four odd vertices, so no such walk exists, whether or not you return to the start. This argument is generally regarded as the birth of graph theory.
Euler's Theorem
Theorem. Let G be a connected multigraph with at least one edge (isolated vertices may be ignored).
(a) G has an Euler circuit if and only if every vertex has even degree.
(b) G has an Euler path that is not a circuit if and only if exactly two vertices have odd degree. Every such path starts at one odd vertex and ends at the other.
Since the number of odd vertices is always even (handshaking), the possibilities are 0 odd vertices (circuit), 2 odd vertices (path), or 4 or more (neither).
Proof of (a), necessity
Follow an Euler circuit. Each time it passes through a vertex v it uses two edges at v (in and out); the start vertex also gets its first edge and its last edge paired up. Since every edge is used exactly once, deg(v) is twice the number of visits, which is even. ∎
Proof of (a), sufficiency
Assume G is connected and every degree is even.
Step 1: a trail that cannot be extended is closed. Start at any vertex v and keep walking along unused edges until you are stuck. Whenever you enter a vertex w ≠ v, you have used an odd number of w's edges (each earlier visit used two, and this arrival used one). Since deg(w) is even, at least one unused edge remains, so you are never stuck at w. Hence you can only get stuck at v, and the trail is closed.
Step 2: splice in more circuits. Let C be the closed trail from Step 1. If C uses every edge, we are done. Otherwise, because G is connected, some vertex u on C still has an unused edge. (If no vertex on C had an unused edge, the edges outside C could not connect to C.) In the graph of unused edges every vertex still has even degree, because C used an even number of edges at each vertex. Apply Step 1 from u to get a closed trail C′ of unused edges, and splice it into C at u: follow C to u, go around C′, then finish C. The result is a longer closed trail. Repeat; since the number of edges is finite, we eventually use them all. ∎
Proof of (b)
If exactly u and v have odd degree, add a new edge e between them (a parallel edge is fine in a multigraph). Now every degree is even, so by (a) there is an Euler circuit. Delete e from it: what remains is an Euler path from u to v. Conversely, along an Euler path every vertex except the two ends has even degree (by the argument in the necessity proof), and if the ends differ, they have odd degree. ∎
Which standard graphs are Eulerian?
Graph | Degrees | Euler circuit when |
|---|---|---|
Kn | n − 1 | n is odd |
Cn | 2 | always |
Km,n | n and m | m and n both even |
Qn | n | n is even |
Wn | hub n, rim 3 | never (rim vertices have degree 3) |
K2 (one edge) has an Euler path but no circuit. K2,n for odd n ≥ 3 has exactly two odd vertices (the two vertices of degree n), so it has an Euler path between them.
Finding an Euler Circuit: Hierholzer's Algorithm
The sufficiency proof is an algorithm, called Hierholzer's algorithm:
Start at any vertex (or at an odd vertex, if you want an Euler path). Walk along unused edges until you get stuck; you are back at the start.
While some vertex on the current circuit has unused edges, start a new closed walk there using only unused edges, and splice it in.
With a stack it runs in O(|E|) time.
Worked example: the bowtie
1 4
│ ╲ ╱ │
│ ╲ ╱ │ edges: 1–2, 2–3, 3–1, 3–4, 4–5, 5–3
│ 3 │ degrees: 1:2, 2:2, 3:4, 4:2, 5:2 (all even)
│ ╱ ╲ │
│ ╱ ╲ │
2 5
Start at 1 and walk: 1 → 2 → 3 → 1. Stuck at 1 (both its edges used). Circuit C = 1, 2, 3, 1.
Vertex 3 on C still has unused edges 3–4 and 3–5. Walk from 3: 3 → 4 → 5 → 3. Closed trail C′ = 3, 4, 5, 3.
Splice C′ into C at 3: 1 → 2 → 3 → 4 → 5 → 3 → 1. All 6 edges used once.
Fleury's algorithm
An older method, Fleury's algorithm, builds the trail one edge at a time with the rule "never cross a bridge of the remaining graph unless you have no other choice". It is easy to apply by hand, but checking for bridges at every step makes it slower (O(|E|²)) than Hierholzer's algorithm.
Worked example: drawing the envelope without lifting the pen
E
╱ ╲
C ───── D Square A–B–D–C with both diagonals A–D and B–C,
│ ╲ ╱ │ plus a roof C–E–D.
│ ╳ │
│ ╱ ╲ │ Degrees: A 3, B 3, C 4, D 4, E 2
A ───── B
Exactly two odd vertices, A and B, so an Euler path exists and must start at one of them and end at the other. One such path: A → D → E → C → D → B → C → A → B. It uses all 8 edges exactly once. Starting from C, D or E is bound to fail, which is why children who try this puzzle often get stuck.
Euler Circuits in Directed Graphs
A directed multigraph with at least one edge has an Euler circuit if and only if deg−(v) = deg+(v) for every vertex and its underlying undirected graph is connected (ignoring isolated vertices). It has an Euler path that is not a circuit if and only if one vertex has out-degree = in-degree + 1 (the start), one vertex has in-degree = out-degree + 1 (the end), all others are balanced, and the underlying graph is connected.
The reason is the same as before: each pass through a vertex uses one incoming and one outgoing edge.
Application: de Bruijn sequences. Is there a cyclic binary string in which every 3-bit pattern appears exactly once as a window? Make a vertex for each 2-bit string and an edge xy → yz for each 3-bit string xyz. Every vertex has in-degree 2 and out-degree 2, so an Euler circuit exists, and it spells out such a string: 00010111. Read cyclically, its windows are 000, 001, 010, 101, 011, 111, 110, 100, all eight patterns once each. The same idea is used in DNA sequence assembly, where overlapping fragments are joined by finding Euler paths.
Application: the Chinese postman problem. A postman must traverse every street at least once and return home, minimising the total distance. If every vertex is even, the answer is an Euler circuit. Otherwise some streets must be repeated; the optimal choice pairs up the odd vertices along shortest paths, and it can be solved in polynomial time.
Hamiltonian Paths and Cycles
The vertex version is named after William Rowan Hamilton, who in 1857 devised a puzzle ("the Icosian game", sold commercially in 1859) asking for a cycle through all 20 vertices of a dodecahedron. Unlike the Euler case, no simple test is known: deciding whether a graph has a Hamiltonian cycle is NP-complete. So we rely on sufficient conditions (which guarantee a cycle), necessary conditions (which can rule one out), and search.
Euler | Hamilton | |
|---|---|---|
Visits every… | edge exactly once | vertex exactly once |
Characterisation | Yes: connected + all degrees even (circuit) | None known; problem is NP-complete |
Algorithm | Hierholzer, O(|E|) | Backtracking / DP, exponential in the worst case |
Real-world version | Chinese postman, street sweeping | Travelling salesman, delivery routing |
The two properties are independent. The bowtie above has an Euler circuit but no Hamiltonian cycle (any cycle through 3 can visit only one of the two triangles). K4 has a Hamiltonian cycle but no Euler circuit (all degrees are 3).
Sufficient conditions: Dirac and Ore
Ore's theorem (1960). If G is a simple graph with n ≥ 3 vertices and deg(u) + deg(v) ≥ n for every pair of non-adjacent vertices u, v, then G has a Hamiltonian cycle.
Dirac's theorem (1952). If G is a simple graph with n ≥ 3 vertices and every vertex has degree at least n/2, then G has a Hamiltonian cycle.
Dirac's theorem follows from Ore's: if every degree is at least n/2, any two vertices have degree sum at least n.
Proof of Ore's theorem. Suppose the theorem is false. Among all counterexamples on n vertices, choose G with the largest number of edges. Adding an edge never breaks the degree condition, so adding any missing edge to G produces a Hamiltonian graph (by maximality). G is not complete (Kn is Hamiltonian for n ≥ 3), so pick non-adjacent u, v. Then G + uv has a Hamiltonian cycle, and it must use uv, so G has a Hamiltonian path u = w1, w2, …, wn = v.
Suppose for some i in 2..n we had u adjacent to wi and v adjacent to wi−1. Then
w1 → w2 → ⋯ → w(i−1) → wn → w(n−1) → ⋯ → wi → w1
is a Hamiltonian cycle in G, a contradiction. So for each i ∈ {2, …, n}, at most one of "u ~ wi" and "v ~ wi−1" holds. Let S = {i : u ~ wi} and T = {i : v ~ wi−1}. Both are subsets of {2, …, n}, which has n − 1 elements, they are disjoint, |S| = deg(u) and |T| = deg(v). Hence deg(u) + deg(v) ≤ n − 1 < n, contradicting the hypothesis for the non-adjacent pair u, v. ∎
These conditions are sufficient but not necessary. Cn for n ≥ 5 is Hamiltonian, yet every degree is 2, far below n/2.
Necessary conditions: proving a graph is NOT Hamiltonian
Degree ≥ 2. A vertex of degree 1 means no Hamiltonian cycle (n ≥ 3).
Forced edges. If deg(v) = 2, both edges at v must be in the cycle. If forced edges close a cycle that misses vertices, or force a third edge at some vertex, there is no Hamiltonian cycle.
No cut vertex. Removing one vertex from a cycle leaves a path, which is connected. So a graph with a cut vertex has no Hamiltonian cycle.
Component test (general form). If a Hamiltonian cycle exists, then for every non-empty set S of vertices, G − S has at most |S| components, because removing |S| vertices from a cycle cuts it into at most |S| pieces.
Bipartite graphs. Every cycle in a bipartite graph alternates sides, so a Hamiltonian cycle needs the two parts to have equal size. Km,n has a Hamiltonian cycle if and only if m = n ≥ 2.
Example. The 3 × 3 grid graph has 9 vertices and is bipartite (colour like a chessboard) with parts of sizes 5 and 4. So it has no Hamiltonian cycle, although it does have a Hamiltonian path (a snake through the rows).
Example. K2,3: removing the 2 vertices of the small part leaves 3 isolated vertices, more than 2 components. No Hamiltonian cycle. A Hamiltonian path exists: start and end in the larger part, e.g. x1, a, x2, b, x3.
The Petersen graph
Vertices 0–9
outer 5-cycle : 0–1, 1–2, 2–3, 3–4, 4–0
spokes : 0–5, 1–6, 2–7, 3–8, 4–9
inner pentagram : 5–7, 7–9, 9–6, 6–8, 8–5
The Petersen graph has 10 vertices, 15 edges and is 3-regular. It is connected, has no cut vertex, and passes the component test, yet an exhaustive search confirms it has no Hamiltonian cycle (it does have a Hamiltonian path). It is the standard example showing that the easy necessary conditions are not sufficient. (Dirac's condition fails too: degree 3 < 10/2.)
Counting Hamiltonian cycles
Kn (n ≥ 3): fix the starting vertex, order the other n − 1 vertices in (n − 1)! ways, and divide by 2 because each cycle is counted once in each direction: (n − 1)!/2. K4 has 3, K5 has 12, K6 has 60.
Kn,n (n ≥ 2): n!(n − 1)!/2. K3,3 has 6, K4,4 has 72.
Hamiltonian cycles in Kn are exactly the possible tours in the travelling salesman problem on n cities, which shows why brute force fails: 20 cities give 19!/2 ≈ 6 × 1016 tours.
Hypercubes and Gray codes
Qn is Hamiltonian for every n ≥ 2. A Hamiltonian cycle in Qn lists all n-bit strings so that neighbours differ in exactly one bit, which is a Gray code. For Q3: 000, 001, 011, 010, 110, 111, 101, 100, back to 000. Gray codes are used in rotary encoders and Karnaugh maps, where changing one bit at a time avoids glitches. (Build Qn's cycle from Qn−1's: list the (n − 1)-bit cycle prefixed with 0, then the same cycle in reverse prefixed with 1.)
Euler and Hamilton in Python
The program below implements Hierholzer's algorithm with an explicit stack (it also works for multigraphs, such as Königsberg) and a backtracking search for Hamiltonian cycles.
from collections import defaultdict
def euler_trail(edges):
"""Return an Euler circuit/path as a vertex list, or None.
Works for multigraphs; assumes the edges form one connected piece."""
adj = defaultdict(list) # vertex -> [(neighbour, edge id)]
for i, (u, v) in enumerate(edges):
adj[u].append((v, i))
adj[v].append((u, i))
odd = [v for v in adj if len(adj[v]) % 2 == 1]
if len(odd) not in (0, 2):
return None
start = odd[0] if odd else edges[0][0]
used = [False] * len(edges)
stack, trail = [start], []
while stack: # Hierholzer's algorithm
v = stack[-1]
while adj[v] and used[adj[v][-1][1]]:
adj[v].pop() # drop edges already used
if adj[v]:
w, i = adj[v].pop()
used[i] = True
stack.append(w) # keep walking
else:
trail.append(stack.pop()) # dead end: add to answer
return trail[::-1]
def hamilton_cycle(n, edges):
"""Backtracking search on vertices 0..n-1."""
nbr = [set() for _ in range(n)]
for u, v in edges:
nbr[u].add(v)
nbr[v].add(u)
path, seen = [0], {0}
def extend():
if len(path) == n:
return 0 in nbr[path[-1]] # can we close the cycle?
for w in sorted(nbr[path[-1]]):
if w not in seen:
path.append(w); seen.add(w)
if extend():
return True
path.pop(); seen.remove(w)
return False
return path + [0] if extend() else None
bowtie = [(1, 2), (2, 3), (3, 1), (3, 4), (4, 5), (5, 3)]
envelope = [("A", "B"), ("A", "C"), ("A", "D"), ("B", "C"), ("B", "D"),
("C", "D"), ("C", "E"), ("D", "E")]
konigsberg = [("A", "B"), ("A", "B"), ("A", "C"), ("A", "C"),
("A", "D"), ("B", "D"), ("C", "D")]
print("bowtie :", euler_trail(bowtie))
print("envelope :", euler_trail(envelope))
print("Konigsberg:", euler_trail(konigsberg))
outer = [(i, (i + 1) % 5) for i in range(5)]
spokes = [(i, i + 5) for i in range(5)]
inner = [(5 + i, 5 + (i + 2) % 5) for i in range(5)]
print("Petersen Hamilton cycle:", hamilton_cycle(10, outer + spokes + inner))
cube = [(a, b) for a in range(8) for b in range(a + 1, 8) if bin(a ^ b).count("1") == 1]
print("Cube Q3 Hamilton cycle :", hamilton_cycle(8, cube))
Output:
bowtie : [1, 3, 5, 4, 3, 2, 1]
envelope : ['A', 'D', 'E', 'C', 'D', 'B', 'C', 'A', 'B']
Konigsberg: None
Petersen Hamilton cycle: None
Cube Q3 Hamilton cycle : [0, 1, 3, 2, 6, 7, 5, 4, 0]
The bowtie circuit goes around the triangles in the opposite order to our hand solution; Euler circuits are rarely unique. In binary, the cube's cycle 0, 1, 3, 2, 6, 7, 5, 4 is 000, 001, 011, 010, 110, 111, 101, 100: exactly the Gray code above. Notice the difference in cost: euler_trail touches each edge a constant number of times, while hamilton_cycle may explore exponentially many partial paths.
Common Mistakes
Mixing up Euler and Hamilton. Euler = every edge once; Hamilton = every vertex once. Memory aid: Euler, Edges.
Forgetting connectivity. Two disjoint triangles have all even degrees but no Euler circuit.
Starting an Euler path at the wrong vertex. With two odd vertices, the path must start at one and end at the other.
Treating Dirac/Ore as "if and only if". Failing their conditions proves nothing (Cn fails them and is Hamiltonian).
Counting Hamiltonian cycles of Kn as n! or (n − 1)!. Fix the start and divide by 2 for direction: (n − 1)!/2.
Counting a loop's degree as 1 when checking Euler conditions in a pseudograph. A loop adds 2.
Interview and GATE-Style Questions
Q1. For which n does Kn have an Euler circuit? For which n does it have a Hamiltonian cycle?
Euler circuit: when n − 1 is even, i.e. n odd (n ≥ 3). Hamiltonian cycle: every n ≥ 3.
Q2. How many distinct Hamiltonian cycles does K5 have?
(5 − 1)!/2 = 24/2 = 12.
Q3. A connected graph has degree sequence (4, 4, 3, 3, 2, 2). Does it have an Euler circuit? An Euler path?
Two vertices have odd degree, so there is no Euler circuit, but there is an Euler path, from one degree-3 vertex to the other.
Q4. Does K4,6 have an Euler circuit? A Hamiltonian cycle?
Degrees are 6 (four vertices) and 4 (six vertices), all even, and it is connected: Euler circuit yes. Hamiltonian cycle no: the parts have different sizes (4 ≠ 6).
Q5. A graph on 10 vertices has minimum degree 5. Must it be Hamiltonian?
Yes, by Dirac's theorem: 5 ≥ 10/2.
Q6. Why is the Euler circuit problem easy and the Hamiltonian cycle problem hard, when they sound so similar?
The Euler condition is local: whether a circuit exists depends only on each vertex's degree and on connectivity, both checkable in linear time, and the proof gives a linear-time construction. Whether a Hamiltonian cycle exists depends on global structure (which vertices can be strung together), and the problem is NP-complete, so no polynomial algorithm is known (one would imply P = NP).
Q7. Show that the graph obtained from K5 by deleting one edge still has a Hamiltonian cycle.
Use Ore's theorem with n = 5. The only non-adjacent pair is the two ends of the deleted edge, each of degree 3, with sum 6 ≥ 5. (Directly: if edge 1–2 is deleted, 1 → 3 → 2 → 4 → 5 → 1 works.)
Summary
Euler circuit ⇔ connected (ignoring isolated vertices) and every degree even. Euler path (not a circuit) ⇔ connected and exactly two odd vertices, which are its ends.
Directed version: in-degree = out-degree everywhere (circuit), or one +1 and one −1 imbalance (path), plus connectivity.
Hierholzer's algorithm finds an Euler circuit in O(|E|) by splicing closed trails; Fleury's rule is "don't cross a bridge unless forced".
Hamiltonian cycle: NP-complete to decide. Sufficient: Dirac (δ ≥ n/2), Ore (deg u + deg v ≥ n for non-adjacent u, v). Necessary: no cut vertex, G − S has at most |S| components, equal parts in a bipartite graph.
Kn has (n − 1)!/2 Hamiltonian cycles; the Petersen graph has none; Qn has Gray-code cycles.
Euler and Hamilton asked how to travel through a graph. The next chapter, Planar Graphs, asks how to draw one: when can a graph be drawn on paper with no edges crossing?