|
|
 from Euler's
paper of 1736
on Königsberg . . . |
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. |
|
|
