National
          Science Foundation
National Curve Bank

Hamilton Circuit

A graph that traverses every vertex exactly once.

Deposit #115

Dr. Peter Avery
MiraCosta College



  from Euler's paper of 1736
on
Königsberg . . .

Be patient.

The dodecahedron depicted both as a plane graph and as a solid.
Hamilton Circuit Animation

Replay animation
dodecahedron solid circuit

Replay animation

dodecahedron thumb link
Dodecahedron animation and other Platonic solids

Tetrahedron

  
tetrahedron
Animation


Cube or hexahedron
 

cube or hexahedron
Animation
Octahedron



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.

Sir William Rowan
                                        Hamilton stamp



Useful Links and References
Hamilton
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.