Euler and Hamilton

Graph
Discrete Math 2
 Content
• Euler graph
• Hamilton graph

2
Euler graph
 The concept of Euler graph (1/2)
• Definition
– simple circuit in a graph G passes through every edges, each of which is
exactly once, is called an Euler circuit.
– simple path in G that passes through every edges, each of which is exactly
once, is called an Euler path.
– The graph is called an Euler graph if it has an Euler circuit.
– A graph with an Euler path is called a semi-Eulerian.

Example 1:

4
 The concept of Euler graph (2/2)
Example 2:

5
Necessary and sufficient conditions for Euler
Circuits (Euler graph)
• Undirected Graph
– The connected Graph G=<V,E> is an Euler graph if and only if every
vertex of G has even degree.
• Directed Graph
– The weakly connected directed Graph G=<V,E> is an Euler graph if and
only if every vertex has out-degree same as in-degree (strongly
connected).

6
 Show that the graph is Euler
• For undirected graphs:
– Check whether the graph is connected or not?
• check DFS(u) = V or BFS(u) = V  connectivity.
– Check whether the degree of all vertices is even?
• For an adjacency matrix, the sum of the elements of row u (column u) is the degree of vertex u.
• For directed graphs:
– Check whether the graph is weakly connected or not?
• Check that the underlying undirected graph is connected, or
• Check if exists vertex u ∈ V so that DFS(u)= V or BFS(u) = V?
– Check if all vertices satisfy the out-degree same as the in-degree?
• For adjacency matrix, the out-degree of vertex u is deg+( u ) is the number of 1s in row u, and
the in-degree of vertex u is deg-( u ) is the number of 1s in column u.

7
 Undirected graph - Example
• Let the undirected graph be represented as an adjacency matrix as
below. Prove it is an Euler graph.
• Because BFS(1) = {1, 2, 6, 3, 5,
7, 4, 11, 8, 10, 12, 9, 13} = V.
Therefore, G is connected.
• Again, we have:
• deg(1) = deg(13) = 2
• deg(2) = deg(3) = 4
• deg(4) = deg(5) = 4
• deg(6) = deg(7) = 4
• deg(8) = deg(9) = 4
• deg(10) = deg(11) = deg(12) = 4

8
 Directed graph - example
• Let the directed graph be represented as an adjacency matrix as
below. Prove it is an Euler graph.

9
 Flor algorithm – Find Euler circuit (manually)

• Starting from a certain vertex u of

G, we arbitrarily browse its edges
ensuring the following two rules:
– Delete the passed edge and also
remove the isolated vertices created.
– At each step, we only cross the
bridge when there is no other
choice.

10
Algorithm for finding Euler’s circuit

11
 Algorithm – Ex (1/3)
• Find an Euler circuit for an
undirected graph
represented as an
adjacency matrix as below.

12
Algorithm -Ex (2/3)

13
Algorithm - Ex (3/3)

14
 Algorithm Implementation
• Init() procedure: reads data of an adjacency matrix.
• Procedure Kiemtra(): Checks whether G is Euler or not.
• Procedure EulerCycle(u): Build an Euler cycle starting at the vertex u.

See illustrative code

15
 Necessary and sufficient conditions for Euler Path
(Semi-Eulerian graph)
• Undirected graph
– The connected undirected graph G =< V , E > is a semi-Eulerian graph if and
only if G has 0 or 2 odd degree vertices.
• G has two odd degree vertices: the Euler path starts at one odd degree vertex and ends
at the other odd degree vertex.
• G has 0 vertices of odd degree: G is an Euler graph.
• Directed Graph
– The weakly connected directed graph G =<V,E> is a semi-Eulerian graph if
and only if:
• It is at exactly 2 vertices u, v such that
deg + (u) - deg - (u)= deg - (v) - deg + (v)= 1.
• Remaming vertices called s  u, s  v satisfy deg+(s)=deg-( s) .
• The Euler path will start at vertex u and end at v.
16
Show that the graph is semi-Eulerian
• For undirected graphs:
– Prove that the given graph is connected
• Use two procedures DFS() or BFS()
– There are 0 or 2 odd degree vertices
• Use properties of graph representation methods to find the degree of
each vertex.
• For directed graphs:
– Show that the given graph is weakly connected
• Use two procedures DFS() or BFS()
– It has:
deg + (u) - deg - (u) = deg - (v) - deg + (v) =1
– The remaining vertices s  u, s  v have deg + (s) = deg - (s).

17
 Example with undirected graph
• Let the undirected graph be represented as an adjacency matrix as below. Prove
that it is a semi-Eulerian graph.

• The sum of the elements in row u is the degree

of the vertex u. So we have:
• deg(1) = deg(13) = 3
• deg(2) = deg(3) = deg(11) = 4
• deg(12) = deg(6) = deg(7) = 4
• deg(8) = deg(9) = 4
• deg(5) = deg(4) = deg(10) = 6
• G is connected and has 2 odd degree vertices
u=1 and u=13, so G is semi-Eulerian.

18
 Directed graph - example
• Let the directed graph be represented as an adjacency matrix as below.
Prove that it is a semi- Eulerian graph.

19
 Euler path finding algorithm (1/2)
• Euler path finding and the Euler circuit finding algorithms differ only in one point,
which is the input of the algorithm.
• The Euler circuit finding algorithm, the input to the algorithm is any vertex u  V .
• The Euler path finding algorithm, the input to the algorithm is the vertex u  V,
satisfying:
– is the first odd degree vertex for undirected graphs.
• If there is no vertex of odd degree, use any vertex.
– is the vertex u  V with deg + (u) - deg - (u) = 1 for directed graphs .

20
Euler path finding algorithm (2/2)

21
 Algorithm - Ex (1/3)
• Find the Euler path on a
weakly connected
directed graph
represented as an
adjacency matrix.

• Then, vertex u has deg + (u) - deg - (u) = 1 is vertex 1 .

22
Algorithm - Ex (2/3)

23
Algorithm - Ex (3/3)

24
 Algorithm Implementation
• Init(): reads data in an adjacency matrix representation.
• Kiemtra(): Checks whether G is semi-Eulerian or not.
• Euler Path(u): Construct an Euler path starting at vertex u (first odd degree
vertex).

See illustrative code

25
 Application: Postman problem
Problem: A postman receives mail at the post office and has to cross some streets
to deliver the mail and then return to the post office. How should the postman
follow the route/path so that the path is the shortest (assuming that all streets of
the same length).
Solution:
– The graph shows the postman's travel diagram as follows: Consider each street as an edge
of the graph, the intersection points (forks, intersections...) between the streets are the
vertices of the graph.
– The above problem is restated as: Let a simple connected undirected graph G=(X, U).
Find the shortest circuit T0 pass through all edges of G.

26
 Application: Postman problem
• The following two cases occur:
– (1): If G is an Euler graph, then the shortest cycle T0 what we are looking for is an Euler
cycle of G, and of length N(U).
– (2): If G is not an Euler graph, then G contains an odd degree vertex and no Euler cycle.
Every cycle that passes through all edges of G will pass through some edge at least
twice. Due to T0 is the shortest cycle, so T0 only pass through each edge at most twice.
• Note: By drawing some more edges parallel to the edges that T0 traversed
twice then G will become an Euler graph GE and T0 is an Euler cycle in GE.

27
 Application: Postman problem
• Let the number of edges that T0 passed through twice is m(G). The number
of edges m(G) is determined by the following algorithm:
– (1): Determine the set of odd degree vertices X0 (G) = {xXdeg(x) is odd }. Let the
number of odd degree vertices (of G) be 2k .
– (2): Partition X0 into k pairs. Let P = {P1 , P2 ,…, Pj } be the set of all possible partitions of
X0 . For each partition Pi , we determine the length of the partition Pi as follows:
d(Pi) =∑ (x,y) Pid(x,y), where d(x,y) = shortest path length from vertex x to vertex y.
– (3): Then m(G) = minPi Pd(Pi).
• Conclusion: shortest cycle T0 passes through all edges of G of length N(U) +
m(G). That cycle is the Euler cycle in the graph GE.

28
 Application: Postman problem
Example: Find the shortest route of the postman
problem with the following graph:
Hamilton graph
 Game "Around the World"
• Suppose there is a 12-sided polyhedron, each face is a regular pentagon (left
figure). Each of the 20 vertices of this polyhedron is named with a city.
• Find a path starting from one city, go along the edges of the polyhedron, visit
the remaining 19 cities, exactly once for each city, finally returning to the
original city.

31
 Hamilton graph - Definition
• The path passes through every vertex of the graph exactly once is called the Hamilton path.
• The circuit starts at a vertex v, passes through all remaining vertices, each vertex exactly once,
then go back to v, is called a Hamiltonian cycle.
• The graph is called a Hamilton graph if there is a Hamilton circuit.
• The graph is called a semi-Hamilton graph if there is a Hamilton path.

32
 Identify Hamilton, semi-Hamilton graph
Theorem 1: Given a simple connected undirected graph G=(X,U) with n vertices. Then,
G is a Hamilton graph if and only if there is one of the following conditions:
– (1) x,yX, deg(x)+deg(y)n (ORE’s Theorem)
– (2) xX, deg(x)≥n/2 (DIRAC’s Theorem)
Consequences:
– (1) A simple connected undirected graph G=(X,U) has n vertices where xX,
deg(x) ≥ (n -1)/2 then G is a semi-Hamilton graph .
– (2) Simple strongly connected directed graph G that, deg+ (x) ≥ n/2 and deg– (x)≥
n/2 then G is a Hamilton graph .
Theorem 2: If k vertices and associated edges are removed from a simple connected
graph G, we have a subgraph that has more than k connected components, then G is not a
Hamilton graph.

34
 Identify Hamilton, semi-Hamilton graphs
Theorem 3: Elimination graph (đồ thị đấu loại) - is a directed graph
in which any two vertices are connected by exactly one arc, is a semi-
Hamilton graph.
Consequence:
– strongly connected elimination graph is Hamilton graph.
Example: D5, D6 (strongly connected elimination graph)

35
 Identify Hamiltonian, half-Hamilton graph

• Some rules for finding the Hamilton circuit (path)

– (1) If G has a vertex has degree less than 2 (ie. G has a hanging or isolated
vertex), then G is not a Hamilton graph.
– (2) If a vertex x has degree 2, then both edges adjacenting to that vertex belong
to the Hamilton cycle (path) that we are looking for.
– (3) While building a Hamiltonian cycle, after taking two edges adjacenting to a
certain vertex, all remaining adjacent edges with that vertex must be removed.
– (4) A Hamiltonian cycle must not contain any subcycles.
• Therefore, every graph that has one vertex adjacenting to three vertices of degree 2 is not a
Hamilton graph.

36
 Identify Hamilton, half-Hamilton graphs
Example 1: Show that the graph G2 has no Hamilton cycle but has a Hamilton path?

• Applying theorem 2, after deleting 5 vertices x2, x4, x7, x10, x12, we get a
subgraph with 6 connected components (G2c ), so G is not a Hamiltonian graph.
37
Identify Hamilton, semi-Hamilton graph
• Example 1: (cont) find the Hamilton path:

• Only 11 edges can be selected and only 12 vertices can be selected, so

this selection can not find the Hamilton path (G2a ).
38
Identify Hamilton, semi-Hamilton graph

• Example 1 : (cont'd) find a Hamilton path

(another choice):

• Choosing 12 edges and passing through 13 vertices, has a Hamilton path of

<x6, x2, x3, x4, x1, x13, x10, x11, x7, x8, x12, x9, x5> (13 vertices, G2b ).
39
 Identify Hamilton, semi-Hamilton graph
Example 2 : G1 is a Hamilton, semi-Hamilton graph? Why?

• Choosing 8 edges and passing through 9 vertices, the Hamilton path

is <3, 6, 9, 7, 4, 1, 2, 5, 8> (G1a ). 40
 Algorithm to find all Hamilton cycles (1/2)
Algorithm ( int k) {
//Liệt kê các chu trình Hamilton của đồ thị bằng cách phát triển dãy đỉnh (X[1], X[2], . . .,
X[k-1] ) của đồ thị G = (V, E) */
for y  Ke(X[k-1]) {//xuất phát từ k=2 (vì cố định đỉnh đầu X[1])
if (k==n+1) and (y == v0) then //đủ đỉnh (X[n]) và cuối (y là kề của đỉnh cuối) trùng với đỉnh
đầu (v0)
Accept(X[1], X[2], . . ., X[n], v0);
else if chuaxet[y] == true{
X[k]=y; chuaxet[y] = false; // duyệt tiếp cây tìm kiếm
Hamilton(k+1);
}
chuaxet[y] = true; //reinit
}
}
41
Algorithm to find all Hamilton cycles (2/2)
• Then, enumeration of Hamilton cycles is done as follows:

42
 Algorithm - Ex
• Graph G=<V, E> (left) => Hamilton cycle search tree (right)

43
Algorithm Implementation

See illustrative code

Students write a program to find the path to Hamilton.

44
 Application: Seat arrangement problem

Problem: There are n delegates from n countries attending the international conference.
They meet once a day by sitting around a round table. How many days must be arranged
and how should it be arranged so that each day, each person has two new friends next to
them?.
Analysis: Consider the graph of n vertices, each vertex corresponds to each participant
the conference, two vertices are adjacent when two respective delegates want to get to
know each other.
– Thus, we have the complete graph Kn. This graph is Hamilton and obviously each Hamilton cycle
is an arrangement as required by the problem.
– The problem becomes finding distinct Hamilton cycles of the complete graph Kn (two Hamilton
cycles are said distinction if they have no common edge).

45
 Application: Seat arrangement problem
Theorem: In Kn (for odd n, n ≥ 3), there are exactly (n-1)/2
distinct Hamilton cycles .
Proof: Kn has n(n-1)/2 edges and each Hamilton cycle has n
edges, so the maximum number of distinct Hamilton cycles is
(n-1)/2.

➢The first Hamilton Cycle: <1; 2; ...; n;1>

➢The vertices are kept fixed, rotate the frame clockwise with rotations of
1/(n-1) of the circle, we get n - 1 Hamilton cycle but only (n-1)/2 different
Hamilton cycles.
➢The last (n-1)/2th Hamilton cycle is <1; n–2; n; n–4; n-1;…;3; 6; 2; 4; 1>.

46
 Application: Seat arrangement problem

Example: List the distinct Hamilton cycles (with no common edge) in the
complete graph K9?

• Note: For even n, every Hamilton cycle of Kn has at least one edge in
common, so the number of distinct Hamiltonian cycles of Kn (n even) is
unique.

47
 Exercise 1
• Given a connected undirected graph G=<V,E>
shown on the right:
a) Prove that the given graph is Euler?
b) Build an algorithm to find an Euler cycle of the
graph starting at the vertex u  V?
c) Find an Euler cycle starting at vertex u=1?
Specify the intermediate result for each
execution step?
d) Find an Euler cycle starting at vertex u=5?
Specify the intermediate result for each
execution step?
e) Write a program to find a Euler cycle of graph
starting at vertex u?

48
 Exercise 2
• Given a connected undirected graph
G=<V,E> shown on the right:
a) Prove that the given graph is semi-
Eulerian?
b) Build an algorithm to find an Euler
path of the graph?
c) Find an Euler path of the graph?
Specify the intermediate result for
each execution step?
d) Write a program to find an Euler path
of a graph?

49
 Exercise 3
• Given a weakly connected directed graph
G=<V,E> shown on the right:
a) Prove that the given graph is Euler?
b) Build an algorithm to find an Euler cycle of
the graph starting at the vertex u  V?
c) Find an Euler cycle starting at vertex u=1?
Specify the intermediate result for each
execution step?
d) Find an Euler cycle starting at vertex u=5?
Specify the intermediate result for each
execution step?
e) Write a program to find an Euler cycle of
the graph starting at vertex u?

50
 Exercise 4
• Let the connected undirected graph be represented as an adjacency list
shown below:
Ke(1) = { 4, 6 }. Ke(5) = { 7, 9 }. Ke(9) = { 3, 5, 7, 13 }.
Ke(2) = { 3, 8, 10, 11}. Ke(6) = { 1, 4, 10, 12 }. Ke(10) = { 2, 3, 6, 12 }.
Ke(3) = { 2, 9, 10, 13 }. Ke(7) = { 5, 9, 11, 13 }. Ke(11) = { 2, 7, 8, 13 }.
Ke(4) = { 1, 6, 8, 12 }. Ke(8) = { 2, 4, 11, 12 }. Ke(12) = { 4, 6, 8, 10 }.
Ke(13) = { 3, 7, 9, 11 }.
• Requirements:
a) Find an Euler cycle starting at vertex u=1? Specify the intermediate result for
each execution step?
b) Find an Euler cycle starting at vertex u=5? Specify the intermediate result for
each execution step?
c) Write a program to find an Euler cycle of the graph starting at vertex u?

51
 Exercise 5
• For a weakly connected directed graph represented as an adjacency list shown
below:
Ke(1) = { 6 }. Ke(5) = { 7 }. Ke(9) = { 5, 7 }.
Ke(2) = { 3, 8}. Ke(6) = { 10, 12 }. Ke(10) = { 2, 3 }.
Ke(3) = { 9, 13 }. Ke(7) = { 11, 13 }. Ke(11) = { 2, 8 }.
Ke(4) = { 1, 6 }. Ke(8) = { 4, 12 }. Ke(12) = { 4, 10 }.
Ke(13) = { 9, 11 }.
• Requirements:
a) Find an Euler cycle starting at vertex u=1? Specify the intermediate result for
each execution step?
b) Find an Euler cycle starting at vertex u=7? Specify the intermediate result for
each execution step?
c) Write a program to find an Euler cycle of the graph starting at vertex u?

52
 Exercise 6
• Is the following graph Hamiltonian, semi-Hamiltonian? Find the
Hamilton cycle, path if any?

53
 Extra Exercises
(bonus)
• Using the algorithm of the Hamilton cycle finding, solve the "Traveller" problem, print
the optimal route. Assume that the cost table is stored in a text file of the following
format:
▪ a[i][j]=-1 is that there is no direct path from i to j.

54