Summary:
Euler
Paths and Circuits
Hamilton Circuits
|
- If each of the vertices of a connected graph has even
degree, then there is an Euler Circuit
for the graph. No matter which vertex is selected as a starting
point, a route may be traced crossing each edge
(path) once and only once, and
ending by returning to the starting vertex. A graph with only even nodes can be
traversed unicursally by a route that both starts and ends at the same
point.
- If a connected graph has exactly two odd
vertices, then an Euler Path
may be traced crossing each path once and only once, but the starting
point must be one of the odd vertices and the ending point will be the
other of the odd vertices. In other words, if a graph has exactly two odd nodes, then
it can be traversed unicursally by starting at one of the odd nodes and
then terminating at the other.
- An Euler graph with more than two odd nodes is said
to be
non-traversable, or multicursal. In other words, routes will have
to be traced more than once. This is another way of saying that
if a graph has more than two vertices of odd degree,
then there is no Euler Path or Circuit for the graph.
- A Hamilton Circuit
traverses each vertex
only once.
- All platonic solids -
the tetrahedron, cube, octahedron, dodecahedron and icosahedron - are
Hamilton Circuits and may
be traversed by crossing each vertex only
once.
|
|
Interesting Facts . . . .
Euler's 1736 paper on the bridges
of Königsberg is widely
recognized as the origin of graph theory.
Euler was prompted to investigate
the 'calculus of position' by a
letter from the mayor of Danzig in Prussia (now Gdansk in Poland), some
80 miles west of Königsberg. Euler replied to the mayor that
this type of problem "bears little relationship to mathematics, and I
do not understand why you expect a mathematician to produce
it......(M)ost noble Sir, you have assigned this question to the
geometry of position, but I am ignorant as to what this new discipline
involves..."
Euler, being the genius that he
was, clearly was captivated. Soon
thereafter he wrote an Italian mathematician . . . .
"A problem was posed to me about an
island in the city of Königsberg, surrounded by a river spanned by
seven bridges, and I was asked whether someone could traverse the
separate bridges in a connected walk in such a way that each bridge is
crossed only once.....This question is so banal, but seemed to be
worthy of attention in that geometry, nor algebra, nor even the art of
counting was sufficient to solve it. In view of this, it occurred
to me to wonder whether it belonged to the geometry of position which
Leibniz had once so much longed for. And so, after some
deliberation, I obtained a simple, yet completely established, rule
with whose help one can immediately decided for all examples of this
kind, with any number of bridges in any arrangement ...."
Leonhard Euler to Giovanni Marinoni
March 13, 1736
|
H
Euler focused on the edges of a graph.
Hamilton followed in Euler's tradition by showing all platonic solids -
the tetrahedron, cube, octahedron, dodecahedron and icosahedron - may
be traversed by crossing each vertex
only once.
|
|
|
Useful Links and References
|
Hamilton
is one of a number of distingished mathematicians born in Ireland.
Note the Euler formula
for polyhedra.
|
Material in
the National Curve Bank related to Sir William Rowan Hamilton
(1805-1865):
< ..//hamilton/hamilton.htm
>
< ..//birthdayindex/aug/aug4hamilton/aug4hamilton.htm
>
< ..//birthdayindex/oct/oct16bridge/oct16bridge.htm
>
< ..//quilt/quilt.htm
>
< ..//birthdayindex/jun/jun16petersen/jun16petersen.htm
>
From Wolfram:
< http://demonstrations.wolfram.com/ManipulablePetersenGraph/
>
|
Brian Hopkins and Robin J.
Wilson, "The Truth about Königsberg," The College Mathematics
Journal, Vol. 35, No. 3, May 2004, pp. 198-207.
|
| Harary, Frank, Graph Theory, Addison–Wesley, 1969.
|
|
|
from Euler's paper of 1736
