Euler Circuits: The bridge problem of K\"onigsberg


  Double Spoke Weels: DW_n

   __   __ 
  X__ A __o    #circuits(DW_1) = 2


  +---o---+
  |__   __|
  A__ X __B    #circuits(DW_2) = 16
  |       |
  +---o---+


  +---o---+
  |__   __|
  A__ X __C    #circuits(DW_3) = 208
  |  | |  |
  o-- B --o


  o-- D --o
  |__| |__|
  A__ X __C    #circuits(DW_4) = 3840
  |  | |  |
  o-- B --o

Recursion:

  C(0) = 0
  D(0) = 1

  C(n+1) = 2n C(n) +      2 D(n)
  D(n+1) =           3(n+1) D(n)

  n   :  0   1   2    3     4      5        6          7           8
  C(n):  0   2  16  208  3840  92928  2795520  100730880  4231987200
  D(n):  1   6  72 1296 31104 933120 33592320 1410877440 67722117120





References:


Leonhard Euler,
  Solutio problematis ad geometriam situs pertinentis,
  Commentarii Academiae Petropolitamae 8, 1736 (1741), 128-140
  - even degree is necessary for an Eulerian circuit.
  - the K\"onigsberg bridge problem.

Martin Gardner,
  M. Gardner's Sixth Book of Mathematical Games from Scientific American,
  Freeman (1971) San Francisco
  (german: Mathematisches Labyrinth, Vieweg, 1979)
  Chapter 10: Graph Theory
  - nointersecting Eulerian path (black-white coloring by T. H. O'Beirne)

L. Saalsch\"utz;  [Report of a lecture.]  
 Schriften der Physikalisch-\"Okonomischen Gesellschaft zu K\"onigsberg 
 16 (1876) 23-24.
 - Sketches Euler's work, listing the seven bridges.  
 Says that a new railway bridge, connecting regions  B  and  C  on Euler's 
 diagram, can be considered within the walkable region.  He shows there
 are  48 x 2 x 4  = 384  possible paths _ the  48  are the lists of regions 
 visited starting with  A;  the  2  corresponds to reversing these lists; 
 the  4 (= 2 x 2)  corresponds to taking each of the two pairs of bridges 
 connecting the same regions in either order,  He lists the  48  sequences 
 of regions which start at  A.  
 D. Singmaster wrote a program to compute Euler paths and tested it on this
 situation.  I find that Saalsch\"utz has omitted two cases, leading to four 
 sequences or  16  paths starting at  A  or  32  paths considering both 
 directions.  That it, his  48  should be  52  and his  384  should be  416.
 (There are 416 direted tours and 208 undirected. )

Horst Sachs, Einf\"uhrung in die Theorie der endliche Graphen, Teil 1,
  B. G. Teubner, Leipzig, 1970

David Singmaster;
 Sources in Recreational Mathematics,
 An Annotated Bibliography, 7th Pre. Ed., Oct. 1999
 Part II, Sect.  5.E.    EULER CIRCUITS AND MAZES

G. Tarry.  G\'eom\'etrie de situation: Nombre de manieres distinctes de
 parcourir en une seule course toutes les all\'ees d'un labyrinthe rentrant,
 en ne passant qu'une seule fois par chacune des all\'ees.
 Comptes Rendus Assoc. Franc. Avance. Sci. 
 15, part 2 (1886) 49-53 & Plates I & II. 
 - General technique for the number of Euler circuits.

J. C. Wilson, On the Traversing of Geometrical Figures,
  Oxford, Oxford University Press, 1905
  (what does this book contain?)

Appendix:

Question: [Sachs, Problem II.2.6]
  The edges of a connected graph can be colored with two colors red or black
  such that every vertex is connected with the same number of red and black 
  edges if and only if every vertex degree is even and the number of edges
  is even.

--
http://www.mathematik.uni-bielefeld.de/~sillke/
mailto:Torsten.Sillke@uni-bielefeld.de