European International Journal of Multidisciplinary Research
and Management Studies
13
https://eipublication.com/index.php/eijmrms
TYPE
Original Research
PAGE NO.
13-18
DOI
OPEN ACCESS
SUBMITED
09 February 2025
ACCEPTED
12 March 2025
PUBLISHED
08 April 2025
VOLUME
Vol.05 Issue04 2025
COPYRIGHT
© 2025 Original content from this work may be used under the terms
of the creative commons attributes 4.0 License.
Euler’s And Hamilton’s
Path Through One-
Dimension Space
Abdul Munir Khirzada
Assistant Professor of Mathematics, Panjshir University, Afghanistan
Sayed Hamid Hashimi
Assistant Professor of Mathematics, Panjshir University, Afghanistan
Abdul Maroof Mashal
Academic Member of Mathematics Curriculum, Ministry of education,
Afghanistan
Abstract:
This article will present a technique for
traversing a graph. Several questions arise here. For
example, can we walk along the edges of a graph
starting from a vertex and returning to it by visiting each
edge of the graph exactly once? Similarly, can we walk
along the edges of a graph starting from a vertex and
returning to it while visiting each vertex of the graph
exactly once? As can be seen, both questions are
identical, but what is important is to consider two
circuits that answer the above questions, namely the
Euler circuit and the Hamilton circuit. Solving the
Hamilton circuit for most graphs is very difficult. In this
section, we will examine these questions and discuss the
difficulty of solving them.
Keywords:
Graph, Euler’s Path, Hamilton’s Paths,
Analysis of path circuit.
Introduction:
To better understand the path, we must
first have a brief introduction to graphs first. Graphs are
discrete structures consisting of vertices and the edges
that connect these vertices. There are different types of
graphs, depending on whether the edges are directed,
whether multiple edges can connect a pair of vertices,
and whether the graphs are cyclic. Traversing on the
graph edges and crossing the vertices a path are
created. Given the importance of these two topics, Euler
and Hamilton paths are one of the fundamental
concepts in graph theory, a branch of mathematics that
European International Journal of Multidisciplinary Research
and Management Studies
14
https://eipublication.com/index.php/eijmrms
European International Journal of Multidisciplinary Research and Management Studies
studies the properties and applications of graphs. We
will give examples to show how graphs can be used as
a model in the context of using graph models to
determine whether it is possible to walk all the streets
of a city without going down a street twice, or whether
a circuit can be implemented on a flat circuit domain.
Graphs with weights assigned to their edges can be
used to solve problems such as finding the shortest
path between two cities in a network. We will also
examine the complexity of Euler and Hamilton paths.
Now we start discussion on Euler and Ha
milton’ path.
Paths: Before we consider the Euler and Hamilton
paths, let us explain the path itself. Suppose we have a
city, we know that a city has a certain area, we consider
the vertices of this area as cities and the edges as
roads, a path is a distance that starts in a city, passes
through several cities, and ends in a city [3].
In [1] a path
∝
in a graph G, with origin v0 and endpoint
vn, is an alternating sequence of n + 1 vertices and n
edges of the form
v0, e1, v1, e2, v2. . . en
–
1, vn
–
1, en, vn
Where each edge ei is located at the vertices vi
–
1 and
vi. And the n edges of a graph are called path lengths.
We show the path
∝
by a sequence of its edges
∝
= (e1,
e2. . . en
–
1, en ) or by a sequence of its vertices
∝
=
(v0, v1, v2, . . . , , vn
–
1, vn) [2].
Theorem
: There is a path from a vertex u to a vertex v
if and only if there exists a simple path from u to v [4].
For more discussion, we describe what a simple path
is.
Simple path
: A path
∝
= (v0, v1, v2, . . . , , vn
–
1, vn) is
simple if all its vertices are distinct. Or a path is called
simple if none of its edges is repeated [1, 6,7 ].
The path
∝
= (v0, v1, v2, . . . , , vn
–
1, vn) is closed if v0
= vn, i.e. its origin (
∝
) is equal to the limit (
∝
). A path is
called a circuit if the path is closed and all vertices except
v0 = vn are distinct. A circuit of length k is called a k-
circuit.
Note: A circuit in a graph G must have length equal to
or greater than three [8].
In general, as it is briefly stated in [6], If u and v are
vertices in the graph G, then the distance between u and
v is represented by d(u, v).
Euler’s Paths and Circuits
: Now we are going to show
how Euler path look like, for a better understanding we
are going to describe with a historical representation of
the path.
Here as it is mentioned in [6], the subject of graph
theory began in the year 1736 when the great
mathematician Leonhard Euler published a paper giving
the solution to its puzzle i.e. Konigsberg Bridges.
Konigsberg Bridges
: Here we consider a city, which is
the city of Konigsberg, which in the 18th century in East
Prussia consisted of two islands and seven bridges. Here
a question arises as follows: a person wants to walk
through the city and, starting from any point in the city,
cross all seven bridges but do not cross any bridge twice
and reach another point in the city? The people of
Konigsberg wrote a letter to the famous Swiss
mathematician Euler about this question. In 1376, Euler
proved that such a walk is impossible.
He replaced the islands and the two sides of the river
with points and the bridges with curves and showed it
in the figure below.
Figure:
Graphical representation of Euler Path
European International Journal of Multidisciplinary Research
and Management Studies
15
https://eipublication.com/index.php/eijmrms
European International Journal of Multidisciplinary Research and Management Studies
Figure:
Bridges of Konigsberg 1786
It is easy to see that such a tour of the city of
Konigsberg is possible only if the multigraph of form (b)
is traversable. But this multigraph has four odd vertices
and is therefore non-traversable. Thus, a pedestrian
cannot circumnavigate the city by crossing each bridge
only once [2, 6].
•
A graph has an Euler circuit if and only if the
degree of every vertex is even.
•
A graph has an Euler path if and only if there
are at most two vertices with odd degree
Since the bridges of Konigsberg graph has all four
vertices with odd degree, there is no Euler path
through the graph. Thus there is no way for the
townspeople to cross every bridge exactly once [5].
Theorem
(Konigsberg Bridge Theorem) (Euler, 1736):
Let G be a connected graph. G has
An Eulerian circuit if and only if each vertex is even.
Definition
: As stated in [2] An Euler circuit in a graph G
is a simple circuit that contains every edge of G. An Euler
path in a graph G is a simple path that contains every
edge of G. In other words, a graph (multiple graph) G is
an Eulerian graph if a traversable closed path has an
Eulerian pat [7]. An Euler circuit is an Euler path which
starts and stops at the same vertex [5].
More example of differential equation;
Example1: In this example, we look at the following
figures and check which of the undirected graphs in
Figures have an Euler circuit? And which of the graphs
that are not Euler circuits have an Euler path?
Figure undirected graph
Solution
: Graph G1 has an Euler circuit, i.e., a, e, c, d,
e, b, a. neither graph G2 nor G3 has an Euler circuit.
However, G3 has an Euler path, i.e., a, c, d, e, b, d, a, b.
G2 does not have an Euler path.
Example2
In this example we consider directed graph.
Which of the directed graphs in bellow Figure have an
Euler circuit? Of those that do not, which have an Euler
path?
European International Journal of Multidisciplinary Research
and Management Studies
16
https://eipublication.com/index.php/eijmrms
European International Journal of Multidisciplinary Research and Management Studies
Figure: Directed graph
Solution: Graph H2 has an Euler circuit, i.e., a, g, c, b, g,
e, d, f, a. Neither H1 nor H3 has an Euler circuit. H3 has
an Euler path, i.e., c, a, b, c, d, b, but H1 does not.
Euler's Theorem
: A finite connected graph G is Eulerian
if and only if the degree of every vertex is even [2].
Now we will discuss the issue of which criterion we
should consider to know in advance whether a graph is
an Euler circuit, path or not. There are simple criteria
for determining whether a multigraph has an Euler
circuit or an Euler path. Euler discovered them when
he solved the famous Konigsberg Bridge problem. We
assume that all graphs discussed in this section have a
finite number of vertices and edges.
What can we say if a connected multigraph has an
Euler circuit? What we can show is that each vertex
must have even degree. To do this, first note that an
Euler circuit starts with a vertex a and continues by
connecting an edge to a, say {a, b). The edge {a, b}
contributes one unit to the degree (a).
Each time the circuit passes through a vertex, it
contributes two units to the degree of the vertex,
because the circuit enters through one edge with this
vertex and exits through another edge. Finally, the
circuit ends where it started, contributing one unit to
the degree (a). Therefore, deg(a) must be even, because
the circuit contributes one unit when it starts, one unit
when it ends, and two units each time it passes through
a (if it does). A vertex other than a has even degree
because the circuit contributes two degrees to its
degree each time it passes through a vertex. We
conclude that if a connected graph has an Euler circuit,
then every vertex must have even degree.
Is this necessary condition also sufficient for an Euler
circuit to exist? That is, if all vertices have even degree,
must an Euler circuit exist in a connected multiple
graph? This question can be answered positively by a
construction [2].
Figure:
Formation of a Euler circuit in graph G
Hamilton’s Path and Circuit:
The discussion above about Eulerian graphs
emphasized edges of travel, here we focus on visiting
vertices. As stated in [1] if every vertex has degree at
least | V | /2, then the graph must be Hamiltonian. A
Hamiltonian circuit or cycle in a graph G, named after
the 19th-century Irish mathematician William
Hamilton (1805
–
1865), is a closed path that visits each
vertex in G exactly once. (Such a closed path must be a
cycle). If G admits a Hamiltonian circuit, G is called a
Hamiltonian graph.
Note that an Eulerian circuit traverses each edge
exactly once, but may repeat vertices, while a
Hamiltonian circuit visits each vertex exactly once, but
may repeat edges. We have established necessary and
sufficient conditions for the existence of paths and
circuits that include each edge of a multigraph exactly
once. Can we do the same for simple paths and circuits
that visit each vertex of the graph exactly once? In
honor of Hamilton, we call a cycle in a graph G that
European International Journal of Multidisciplinary Research
and Management Studies
17
https://eipublication.com/index.php/eijmrms
European International Journal of Multidisciplinary Research and Management Studies
contains each vertex in G exactly once, except for the
starting and ending vertex that appears twice, a
Hamiltonian cycle [2, 3].
Definition
: A simple path in a graph G, or Hamiltonian
graph, is a graph with a closed path that visits each
vertex exactly once. Such a path is a cycle, called a
Hamiltonian cycle. Note that an Eulerian cycle visits
each edge only once, but a vertex may be repeated, but
a Hamiltonian cycle visits each vertex only once (except
the initial and terminal vertices), but the edges may not
[2].
To be noticed, A Hamiltonian graph cannot contain a
vertex of degree zero or one [1]. A simple circuit in a
graph G that visits each vertex exactly once is called a
Hamiltonian circuit [2].
Figure a :
Homilton’s circle
Figure b :
Eular’s circle
Example
: Now look at figure below, which of the
simple graphs has a Hamiltonian circuit or a
Hamiltonian path?
Solution: G1 has a Hamiltonian circuit, a, b, c, d, e, a.
But G2 has a Hamiltonian path, that is, a, b, c, d, and
does not form a circuit. G3 It has neither a Hamiltonian
circuit nor a Hamiltonian path, because any path that
includes all vertices must have one of the edges {a, b},
{e, f}, and {c, d} more than once.
Example: showing that the graph G does not have a Hamiltonian circuit.
As stated in [8], We solve this example by considering
the properties of the subgraph which states as follows:
i) A subgraph H (V ′, E′) of G(V , E) is called the subgraph
induced by its vertices V ′ if its edge set E′ contains all
edges in G whose endpoints belong to vertices in H .
(ii) If v is a vertex in G, then G − v is the subgraph of G
obtained by deleting v from G and deleting all edges in
G which contain v.
(iii) If e is an edge in G, then G − e is the subgraph of G
obtained by simply deleting the edge e from G.
Suppose there is a connected subgraph H of G such that
H has five vertices (a, b, c, d, and e) and five edges and
such that every vertex of H has degree 2. Since the
degree of b in G is 4 and every vertex of H has degree
2, two edges incident on b must be removed from G to
create H. Edge {a, b} cannot be removed because if it
were, vertex a would have degree less than 2 in H.
Similar reasoning shows that edges {e, b}, {b, a}, and {b,
European International Journal of Multidisciplinary Research
and Management Studies
18
https://eipublication.com/index.php/eijmrms
European International Journal of Multidisciplinary Research and Management Studies
d} cannot be removed either. It follows that the degree
of b in H must be 4, which contradicts the condition
that every vertex in H has degree 2 in H. Hence no such
subgraph H exists, and so G does not have a
Hamiltonian circuit [6].
Theorem
: by [7], Let G be a connected graph with n
vertices. Then G is Hamilto
nian if n ≥ 3 and n ≤ deg (v)
for each vertex v in G.
CONCLUSION
In this article, we described Euler’s and Hamilton’s
paths with the help of Graph formation, and at the
same time, variable examples were presented to
better understand the mentioned Topic. What was
received from this article is that Euler’s path only
focused on edges that is Eulerian circuit traverses each
edge exactly once, but may repeat vertices, while a
Hamiltonian circuit visits each vertex exactly once.
REFERENCE
Gary Haggard, John Schlipf & Sue Whiteside, Discrete
Mathematics for Computer Science, Thomson Learning
Academic Resource Center, 2006.
H. Rosen Kenneth, Discrete Mathematics and Its
Applications, Seventh Edition, Monmouth University,
Published by McGraw-Hill, a business unit of The
McGraw-Hill Companies, Inc., 1221 Avenue of the
Americas, New York, NY 10020, 2012.
Johnson Baugh, Richard, Discrete Mathematics, Eight
edition, DePaul University, Chicago, 1941. Copyright ©
2018, 2009, 2005 by Pearson Education.
Lipchitz−Lipson. Schaum’s, Outline of Theory and
Problems of Discrete Math, Department of
Mathematics, The McGraw−Hill Companies, 2004.
Oscar Levin, Discrete Mathematics An Open
Introduction, School of Mathematical Science
University of Northern Colorado, 2013.
S. Epps Susanna, Discrete mathematics with
applications,
fifth
edition, DePaul
University,
University of Nebraska Lincoln, Printed in the United
States of America, 2018.
Seymour Lipchitz & Marc Lars Lipson, Theory and
Problems of Discrete Mathematics, Third edition, by
The McGraw-Hill Companies, 2007.
