Graphs
Chapter 10
Copyright © McGraw-Hill Education. All rights reserved. No reproduction or distribution without the prior written consent of McGraw-Hill Education.
Euler and Hamiltonian
Graphs
Section 10.5
Section Summary
⚫ Euler Paths and Circuits
⚫ Hamilton Paths and Circuits
⚫ Applications of Hamilton Circuits
Euler Paths and Circuits
⚫ The town of Kӧnigsberg, Prussia (now Kalingrad, Russia) was divided into
four sections by the branches of the Pregel river. In the 18th century seven
bridges connected these regions.
⚫ People wondered whether whether it was possible to follow a path that
crosses each bridge exactly once and returns to the starting point.
⚫ The Swiss mathematician Leonard Euler proved that no such path exists.
This result is often considered to be the first theorem ever proved in graph
theory.
Multigraph
Model of the
Bridges of
Kӧnigsberg
The 7 Bridges of Kӧnigsberg
Euler Paths and Circuits
(continued)
Definition: An Euler circuit in a graph G is a simple circuit
containing every edge of G. An Euler path in G is a simple path
containing every edge of G.
Example: Which of the undirected graphs G1, G2, and G3 has a Euler
circuit? Of those that do not, which has an Euler path?
Solution: The graph G1 has an Euler circuit (e.g., a, e, c, d, e, b, a).
But, as can easily be verified by inspection, neither G2 nor G3 has an
Euler circuit. Note that G3 has an Euler path (e.g., a, c, d, e, b, d, a,
b), but there is no Euler path in G2, which can be verified by
inspection.
Necessary Conditions for Euler Circuits
and Paths
⚫ An Euler circuit begins with a vertex a and continues with an edge incident
with a, say {a, b}. The edge {a, b} contributes one to deg(a).
⚫ Each time the circuit passes through a vertex it contributes two to the
vertex’s degree.
⚫ Finally, the circuit terminates where it started, contributing one to deg(a).
Therefore deg(a) must be even.
⚫ We conclude that the degree of every other vertex must also be even.
⚫ By the same reasoning, we see that the initial vertex and the final vertex of
an Euler path have odd degree, while every other vertex has even degree.
So, a graph with an Euler path has exactly two vertices of odd degree.
⚫ In the next slide we will show that these necessary conditions are also
sufficient conditions.
Sufficient Conditions for Euler Circuits
and Paths
Suppose that G is a connected multigraph with ≥ 2 vertices, all of even degree. Let x0 = a be
a vertex of even degree. Choose an edge {x0, x1} incident with a and proceed to build a simple
path {x0, x1}, {x1, x2}, …, {xn-1, xn} by adding edges one by one until another edge can not be
added.
We illustrate this idea in the graph G here. We
begin at a and choose the edges
{a, f}, {f, c}, {c, b}, and {b, a} in succession.
⚫ The path begins at a with an edge of the form {a, x}; we show that it must terminate at a with
an edge of the form {y, a}. Since each vertex has an even degree, there must be an even
number of edges incident with this vertex. Hence, every time we enter a vertex other than a,
we can leave it. Therefore, the path can only end at a.
⚫ If all of the edges have been used, an Euler circuit has been constructed. Otherwise, consider
the subgraph H obtained from G by deleting the edges already used.
In the example H consists of the
vertices c, d, e.
Sufficient Conditions for Euler Circuits
and Paths (continued)
⚫ Because G is connected, H must have at least one vertex in common with the circuit that has
been deleted.
In the example, the vertex is c.
⚫ Every vertex in H must have even degree because all the vertices in G have even degree and
for each vertex, pairs of edges incident with this vertex have been deleted. Beginning with the
shared vertex construct a path ending in the same vertex (as was done before). Then splice
this new circuit into the original circuit.
In the example, we end up with the circuit a, f, c, d,
e, c, b, a.
⚫ Continue this process until all edges have been used. This produces an Euler circuit. Since
every edge is included and no edge is included more than once.
⚫ Similar reasoning can be used to show that a graph with exactly two vertices of odd degree
must have an Euler path connecting these two vertices of odd degree
Algorithm for Constructing an
Euler Circuits
In our proof we developed this algorithms for constructing a
Euler circuit in a graph with no vertices of odd degree.
procedure Euler(G: connected multigraph with all vertices of even degree)
circuit := a circuit in G beginning at an arbitrarily chosen vertex with edges
successively added to form a path that returns to this vertex.
H := G with the edges of this circuit removed
while H has edges
subcircuit := a circuit in H beginning at a vertex in H that also is
an endpoint of an edge in circuit.
H := H with edges of subciruit and all isolated vertices removed
circuit := circuit with subcircuit inserted at the appropriate vertex.
return circuit{circuit is an Euler circuit}
Necessary and Sufficient Conditions for
Euler Circuits and Paths (continued)
Theorem: A connected multigraph with at least two vertices has
an Euler circuit if and only if each of its vertices has an even
degree and it has an Euler path if and only if it has exactly two
vertices of odd degree.
Example: Two of the vertices in the multigraph model of the
Kӧnigsberg bridge problem have odd degree. Hence, there is no
Euler circuit in this multigraph and it is impossible to start at a
given point, cross each bridge exactly once, and return to the
starting point.
Euler Circuits and Paths
Example:
G1 contains exactly two vertices of odd degree (b and d). Hence it has an
Euler path, e.g., d, a, b, c, d, b.
G2 has exactly two vertices of odd degree (b and d). Hence it has an Euler
path, e.g., b, a, g, f, e, d, c, g, b, c, f, d.
G3 has six vertices of odd degree. Hence, it does not have an Euler path.
Applications of Euler Paths and
Circuits
⚫ Euler paths and circuits can be used to solve many practical
problems such as finding a path or circuit that traverses each
⚫ street in a neighborhood,
⚫ road in a transportation network,
⚫ connection in a utility grid,
⚫ link in a communications network.
⚫ Other applications are found in the
⚫ layout of circuits,
⚫ network multicasting,
⚫ molecular biology, where Euler paths are used in the sequencing
of DNA.
William Rowan
Hamilton (1805-
1865)
Hamilton Paths and Circuits
⚫ Euler paths and circuits contained every edge only once. Now we look at paths and circuits that contain
every vertex exactly once.
⚫ William Hamilton invented the Icosian puzzle in 1857. It consisted of a wooden dodecahedron (with 12
regular pentagons as faces), illustrated in (a), with a peg at each vertex, labeled with the names of
different cities. String was used to used to plot a circuit visiting 20 cities exactly once
⚫ The graph form of the puzzle is given in (b).
⚫ The solution (a Hamilton circuit) is given here.
Hamilton Paths and Circuits
Definition: A simple path in a graph G that passes through every vertex
exactly once is called a Hamilton path, and a simple circuit in a graph G
that passes through every vertex exactly once is called a Hamilton circuit.
That is, a simple path x0, x1, …, xn-1, xn in the graph G = (V, E) is called a
Hamilton path if V = {x0, x1, … , xn-1, xn } and xi ≠ xj for 0≤ i < j ≤ n, and
the simple circuit x0, x1, …, xn-1, xn, x0 (with n > 0) is a Hamilton
circuit if x0, x1, … , xn-1, xn is a Hamilton path.
Hamilton Paths and Circuits
(continued)
Example: Which of these simple graphs has a Hamilton
circuit or, if not, a Hamilton path?
Solution: G1 has a Hamilton circuit: a, b, c, d, e, a.
G2 does not have a Hamilton circuit (Why?), but does
have a Hamilton path : a, b, c, d.
G3 does not have a Hamilton circuit, or a Hamilton path.
Why?
Necessary Conditions for
Hamilton Circuits Gabriel Andrew Dirac
(1925-1984)
⚫ Unlike for an Euler circuit, no simple necessary and sufficient
conditions are known for the existence of a Hamiton circuit.
⚫ However, there are some useful necessary conditions. We describe
two of these now.
Dirac’s Theorem: If G is a simple graph with n ≥ 3 vertices such
that the degree of every vertex in G is ≥ n/2, then G has a Hamilton
circuit.
Ore’s Theorem: If G is a simple graph with n ≥ 3 vertices such that
deg(u) + deg(v) ≥ n for every pair of nonadjacent vertices, then G
has a Hamilton circuit.
Øysten Ore
(1899-1968)
Applications of Hamilton Paths and
Circuits
⚫ Applications that ask for a path or a circuit that visits each
intersection of a city, each place pipelines intersect in a utility
grid, or each node in a communications network exactly once,
can be solved by finding a Hamilton path in the appropriate
graph.
⚫ The famous traveling salesperson problem (TSP) asks for the
shortest route a traveling salesperson should take to visit a set
of cities. This problem reduces to finding a Hamilton circuit
such that the total sum of the weights of its edges is as small as
possible.
⚫ A family of binary codes, known as Gray codes, which
minimize the effect of transmission errors, correspond to
Hamilton circuits in the n-cube Qn. (See the text for details.)