11.5 Euler and Hamilton Problems

Sections 11.3 and 11.4 optimized a route or a connection backbone by edge count or total weight. This section asks a different kind of route question: can one trip cover every required part of a graph exactly once?

There are two fundamentally different versions. An Euler route covers every edge; a Hamilton route visits every vertex. Keeping that distinction visible prevents many common mistakes.

Euler trails cover every edge

An Euler trail is a trail that uses every edge of the graph exactly once. Recall that a trail may revisit vertices but cannot repeat an edge.

An Euler circuit is an Euler trail that returns to its starting vertex. It is therefore a closed trail using every edge exactly once.

A connected graph with an Euler circuit is called Eulerian. When isolated vertices are present, they do not participate in any edge route, so the precise condition concerns the component containing all nonisolated vertices.

The classic motivation is the Seven Bridges of Königsberg: each land region becomes a vertex and each bridge becomes an edge. Crossing every bridge once asks for an Euler trail, not a shortest path.

Degree parity controls Euler routes

An integer is even when it is divisible by $2$ and odd otherwise. Degree parity determines whether an undirected graph can have an Euler route.

Imagine arriving at an internal vertex during a trail. One unused incident edge brings you in, and a different unused edge must take you out. The used edges at that vertex are paired as arrival and departure.

In an Euler circuit, the starting vertex also has its final arrival paired with its first departure. Therefore every vertex has even degree.

In an open Euler trail, the start has one extra departure and the end has one extra arrival. Exactly those two vertices have odd degree; every other vertex has even degree.

This gives the complete undirected criterion:

• an Euler circuit exists exactly when all nonisolated vertices belong to one connected component and every vertex has even degree;

• an open Euler trail exists exactly when all nonisolated vertices belong to one connected component and exactly two vertices have odd degree;

• with more than two odd-degree vertices, no Euler trail exists.

The Handshake Lemma already guarantees that the number of odd-degree vertices is even, so possible counts begin $0,2,4,6,\ldots$.

Constructing an Euler route

The degree test decides existence, but we still need to build the route. Hierholzer's algorithm does this:

1. if there are two odd-degree vertices, start at either one; otherwise start at any vertex incident with an edge;

2. follow unused edges until no unused incident edge remains;

3. if every edge has been used, stop;

4. otherwise, find a vertex already on the route that still touches an unused edge;

5. build another closed unused-edge trail from that vertex and splice it into the existing route.

Why can an unfinished circuit not become trapped at a different even-degree vertex? Every arrival uses one edge, leaving the remaining unused incident edges in pairs. Only the permitted odd endpoint can have an unmatched arrival or departure.

For a graph with edges

all degrees are even: $\deg(C)=4$ and the other degrees are $2$. One Euler circuit is

Vertex $C$ appears twice, which is allowed; every edge appears exactly once.

Deliver parcels by drawing one continuous route across every street exactly once. Used streets seal behind the courier, vertex degree gates predict legal starts, and a route-splicing tool lets learners recover from locally attractive dead ends.

Hamilton paths cover every vertex

A Hamilton path visits every vertex exactly once. A Hamilton cycle visits every vertex exactly once and returns to its starting vertex; only the repeated start/end occurrence is allowed.

A Hamilton route does not need to use every edge. Unused edges are irrelevant as long as consecutive visited vertices are adjacent.

Compare the objectives:

A cycle graph on $n\ge3$ vertices has both an Euler circuit and a Hamilton cycle. Other graphs may have one but not the other. A star with at least three leaves has many repeated-center edge routes but no Hamilton path: after visiting one leaf and passing through the center to a second leaf, the route cannot reach another leaf without revisiting the center.

Necessary conditions are not complete tests

Some observations can prove that a Hamilton cycle is impossible:

• every vertex on a Hamilton cycle uses two incident cycle edges, so a vertex of degree less than $2$ rules out a Hamilton cycle;

• a Hamilton cycle remains a path after any one vertex is deleted, so deleting one vertex cannot split the remaining graph into multiple nonempty pieces;

• a bridge cannot lie on a cycle, so a graph with a bridge cannot have a Hamilton cycle that visits vertices on both sides.

These are necessary conditions: every graph with a Hamilton cycle must satisfy them. They are not sufficient; passing them does not guarantee a Hamilton cycle.

This contrasts sharply with the Euler degree criterion, which is both necessary and sufficient.

Backtracking search for Hamilton routes

For a small graph, we can systematically search for a Hamilton path:

1. choose a starting vertex and mark it used;

2. extend the current path to an adjacent unused vertex;

3. if every vertex is used, a Hamilton path has been found;

4. if no unused neighbor is available too early, undo the latest choice;

5. try a different unused neighbor.

Undoing a choice and trying another branch is backtracking, a search technique connected to the recursion trees of Chapter 7.

For a Hamilton cycle, the final vertex must also be adjacent to the start. A partial path can be rejected early when it strands an unvisited vertex with no available connection, or when the remaining unused vertices split into pieces that the path cannot join.

In the worst case, the search may examine arrangements of many vertices. Chapter 6 showed that $n$ distinct objects have $n!$ permutations, explaining why brute-force Hamilton search grows rapidly. Unlike Euler routes, no simple parity rule solves every Hamilton instance.

A constructive example

Let

with edges

Starting at $A$, the partial choice $A,B,C$ can extend to $D$, then $E$, and edge $EA$ closes the route. Thus

is a Hamilton cycle. It uses five of the graph's eight edges; Hamilton's requirement concerns vertices, not edge coverage.

Plan a festival tour that visits every venue once. Build the visit order on the map, undo branches that strand venues, activate structural obstacles such as a leaf or articulation bottleneck, and compare successful Hamilton tours with Euler edge coverage.

Two coverage questions, two kinds of reasoning

Euler problems ask about edges and have a complete degree-parity test plus an efficient construction algorithm. Hamilton problems ask about vertices; simple conditions can reject some graphs, but constructive search may still be necessary.

Section 11.6 turns from routes to resource conflicts and drawings. Vertex coloring will separate adjacent objects, while planarity will ask whether all edges can be drawn without crossings.