Counting Eulerian Circuits and Tours Torsten Sillke, 1999-04-04 last update: 2004-05-23 Problem Nikolaus: Draw the Nikolaus puzzle without lifting your pencil off the paper or going along the same line twice. Count the number of possibilities. A mathematician would say: How many Eulerian paths has this figure? (X is a crossing point of the two edges AD and BC but no vertex of the graph.) E / \ / \ C-----D the Nikolaus graph |\ /| | \ / | | X | | / \ | |/ \| A-----B In Germany this problems is known under the name 'Das Haus vom Nikolaus' (The house of the St Nicholas). A person drawing this figure is saying the rhyme Das ist das Haus vom Ni-ko-laus at each stroke one syllable. Solution I: sio Deleting the vertex E we get the symmetrical graph K_4 C-----D the K_4 graph (the complete graph with 4 vertices) |\ /| | \ / | | X | | / \ | |/ \| A-----B This graph can be covered by two paths. There are three types of path pairs (A-B, C-D), (A-C, B-D), and (A-D, B-C). Each type have the same number of possible configuration as the graph is symmetric. We have 66 path pairs for the K_4 (see the problem below). The second and third type can be conneted via vertex E to a single path an Eulerian tour of the Nikolaus graph. So there are 44 undirected pathes. Solution II: sio Contract the path CED to an edge CD. Add a further edge AB. So each Eulerian circuit in the resulting graph corresponds to an Eulerian tour in the original one. C=====D the even Nikolaus graph |\ /| ( the '===' are two edges. ) | \ / | | X | | / \ | |/ \| A=====B Now we reduce the problem by divide and conquer by cutting the (multi)graph in the middle. x=====y ( the '===' are two edges. ) |\ /| A B C D A C B D |/ \| x=====y So we are left with the problem to count the number of possibilities to cover the following graph with two pathes. a b There are 3*3 ways to connect the edges at x and y pairwise. \ / x ab|cd = 4 The number of pairs of paths ab and cd. ( ) ac|bd = 2 The number of pairs of paths ac and bd. y ad|bc = 2 The number of pairs of paths ad and bc. / \ 1 The number of possibilities for a cycle c d Now combine the all combinations of the top and the bottom graph. top: AB|CD AD|BC AC|BD botton AC|BD 4*4 4*2 0 The entry is 0 if we get two AD|BC 2*4 0 2*2 circuits which occur in one of AB|CD 0 2*2 2*2 three cases. In total these are 44 possibilities. (control calculation (4+2+2)*(4+2+2) - 4*2 - 2*2 - 2*4 = 44) Solution III: [Tarry] (see problem K_5) Tarry's reduction is described in detail in [Ahrens], [Lucas], and [Rouse Ball]. He wanted to count all cyclic domino arrangments for the double 4 set. Problem K_4: How many decompositions into two paths and possibly some cycles has the K_4? (X is a crossing point of the two edges AD and BC but no vertex of the graph.) C-----D the K_4 graph (the complete graph with 4 vertices) |\ /| | \ / | | X | | / \ | |/ \| A-----B Solution: sio On each vertex there are 3 ways to connect two edges. Therefore there are CD = 3*3*3*3 = 81 two path and cycle decompositions. As we must have two paths the maximal number of edges in the cycles can be 4 but the smalles cycle is a C_3. Therefore we the following case. case A: two pathes case B: C_3, P_3, P_2 case C: C_4, P_2, P_2 The case B and C are easy to determine. #(C_3, P_3, P_2) = 12 There are 4 ways selecting the C_3 and 3 ways to select a further edge. #(C_4, P_2, P_2) = 3 There are 3 ways to select two independent edges. The complement if the C_4. The remaining case A must cointain the rest. #(two pathes) = CD - #(C_3, P_3, P_2) - #(C_4, P_2, P_2) = 66. Classification of the Eulerian path pairs: (WLoG connect A-C and B-D) The classification is according the path length. Two diagrams are connected with an arrow if they are related via a permutation of the vertices. (In the ascii the vertices are double drawn to better show the paths.) case P_4, P_4: C-----D x-----x C D| (AC) |x x |\ / | <----> | \ /| | X | | X | |/ \ | <----> | / \| A B| (BD) |x x A-----B x-----x case P_3, P_5: C-----D x-----x |C D| (AC) |x x | \ / | <----> | \ / \ | X | | X | | / \ | | / \ | |/A--B| |/x--x| A B x x ^ ^ | (BD) | (BD) v v x x x x |\x--x| (AC) |\x--x| | \ / | <----> | \ / | | X | | X | | / \ / | / \ | |x x |x x| x-----x x-----x case P_2, P_6: C /---D x /---x |C D (AC) |x x| | \ /| <----> | \ / | | X | | X | | / \| <----> | / \ | |A B (BD) |x x| A \___B x \___x C D x /---x |C---D| (AC) |x x| | \ / | <----> | \ / | | X | | X | | / \ / | / \ | |A B |x---x| A \___B x x ^ ^ | (BD) | (BD) v v x x x /---x |x---x| (AC) |x x | \ / | <----> | \ / \ | X | | X | | / \ | | / \ | |x x| |x---x| x \___x x x The transformation (AB)(CD) is the vertical reflection and generates 10 further pairs of paths. The P_4, P_4 case is symmetric. So we have in total the 22 pairs of paths. Problem K_5: [Dudeney, 1931][Dudeney, 1958] How many Eulerian circiuts has the K_5? Solution I: sio There are 132 undirected circuits. How many cycle decompositions has the K_5? On each vertex there are 3 ways to connect the edges pairwise. Therefore there are CD = 3*3*3*3*3 = 243 cycle decompositions. The following cycle sizes are possible: #(C_5,C_5) = 6 There are 5!/(5*2) = 12 possible C_5. The complement is a C_5 too. This reduces the number of C_5 pair by a factor two. #(C_3,C_3,C_4) = 15 There are 5 * 4!/(4*2) = 15 possible C_4 (5 ways for the unused vertex). The complement determines in a unique way two C_3. #(C_4,C_6) = 30 There are 5 * 4!/(4*2) = 15 possible C_4 (5 ways for the unused vertex). The complement determines in a unique way two C_3. The other two possibilities give a C_6. #(C_3,C_7) = 60 There are 10 possible C_3 (5C2 ways for two unused vertces). There are 3*3 ways to connect the other edges pairwise. So we have 90 ways for a C_3 in a fixed position and some other cycles. But the other cycles can only be a C_7 or a C_3, C_4 pair. In this way the (C_3,C_3,C_4) are double counted as they contain two C_3. Therefore we have 90 = #(C_3,C_7) + 2*#(C_3,C_3,C_4). #(C_10) = 132 The remaining case must cointain the rest. #(C_10) = CD - #(C_3,C_7) - #(C_4,C_6) - #(C_3,C_3,C_4) - #(C_5,C_5). Solution II: sio Divide and conquer method. We already know that the K_4 has 66 pairs of Eulerian paths. Now add the fifth vertex. The four additional edges can be connected in two ways to form a single Eulerian circuits. So there are 2*66 = 132 Eulerian circuits for the K_5. Solution III: [Tarry] Reduction mehtod. Select a vertex. There are three ways to connect its four adjacent edges pairwise. The reduced graph is in each case the even Nikolaus graph. We know that the even Nikolaus graph has 44 Eulerian circuits. So there are 3*44 = 132 Eulerian circuits for the K_5. Tarry's reduction is described in detail in [Ahrens] and [Rouse Ball]. He wanted to count all cyclic domino arrangments for the double 4 set. Problem Hopscotch: [Dudeney 1931 Problem 333][Slocum, 1996 p32] Draw the hopscotch puzzle without lifting your pencil off the paper or going along the same line twice. Count the number of possibilities. A---B---C---D /|\ /| | | ( | X | | | \|/ \| | | E---F---G---H Solution: sio Dissect the graph by replacing the pair of edges BC, FG by the pair BF, CG. The path CDHG can be replaced by a further edge CG. This gives the multigraph. A---B C /|\ /|\ /|\ ( | X | ) ( | ) \|/ \|/ \|/ E---F G The first component has 44 Eulerian cirlces, as it is the even Nikolaus graph. The second component has 6 Eulerian tours. Therefore we have 44*6 = 264 combinations. Switching the edges back each combination gives us an Eulerian tour of the hopscotch graph. Problem K_5 alternating: [Mittenzwey, 1880 problem 269] Draw the K_5 as a regular pentagon with all its diagonals. Color the sides black and the diagonals red. Find an alternating Eulerian circuit. Solution: sio At each vertex there are two possibilities to connect edges of different colors. Therefore there are 2*2*2*2*2 = 32 different coverings with sets of alternating circuits. Alternating cycle decomposition can be a C_10 or the pair (C_4, C_6) as the cycle length must be even. The number of alternating cyles #(C_4, C_6) = 10 as there are 5 ways to select 4 vertices for the C_4. Given 4 vertices there is only one alternating C_4. The complement has two different C_6 which are both alternating. Therefore we have 32 - #(C_4, C_6) = #(C_10) = 22 alternating 10-cycles. There are two symmetric tours: (Let the vertices be 0..4) - 0-1-4-0-3-4-2-3-1-2-0 (differences are 1, 3 alternating) - 0-1-3-4-1-2-4-0-2-3-0 (differences are 1, 2 alternating) Problem Octahedron: How many Eulerian circuits has the graph of the octahedron? How many of this circuits have no crossings (only knock knees allowed)? Notice that this is related to the 'even Nikolaus' graph. A---B Identify the two vertices F to get the octahedron. /|\ /|\ F | E | F \|/ \|/ C---D Solution (part a): There are 3*3 ways to connect the edges at the top vertex pairwise and at the bottom vertex. Which graphs do we get? A---B 5 times the 'even Nikolaus' graph /|\ /|\ ( | X | ) \|/ \|/ D---C A=====B 2 times graph A. || || || || || || D=====C A-----B 2 times graph B. ||| ||| ||| ||| ||| ||| D-----C Eulerian circuits of graph A: case a: circuits having a u-turn. There are 4 vertices where the u-turn can occur. We are left with a pathlike graph: V===W===X===Y===Z. There are 2*2*2 possibilities for connecting the edges at W, X, and Y (without creating a further u-turn pair and thereby disconnecting the circuit). So we get 4*8 = 32 circuits in this case. case b: circuits having no u-turn. At each vertex there are two possibilites for connection. Half of them give one circuit the other half two circuits. (switching the edges at one vertex is a bijection between the one and the two circuit case.) So we get 2*2*2*2/2 = 8 circuits in this case. The number of Eulerian circuits of graph A is 32+8 = 40. Eulerian circuits of graph B: Dissect the graph by replacing the pair of edges AB, CD by the pair AD, BC. So we have four edges between A and D as well as B and C. These graphs have 3! = 6 Eulerian circuits. Now combine the the two components. The number of Eulerian circuits of graph B is 6*6 = 36. Counting together we get 5*44 + 2*40 + 2*36 = 372 Eulerian circuits. Problem 3 Square - Prism: How many Eulerian circuits has the graph 3 Squares? +--------+ | | +--A-----+ | A=======B | | | | |\ /| +--E--C--+ | | | C===D | | | | | | | |/ \| | | +--D--B--+ E=======F | | | | | +-----F--+ This is the same as the prism | | +--------+ Solution: The reduction after Tarry gives A===B 2 times graph N5. |\ /| | C | circles(N5) = 120 |/ \| D===E A=====B 2 times graph A. || || || || circles(A) = 40 || || D=====C Counting together we get 2*120 + 2*40 = 320 Eulerian circuits. Problem concentric circles: [Schuh, Section 289] How many Eulerian pathes A to B has the graph? ___________ / _______ \ / / ___ \ \ / / / \ \ \ A--X--X--X---X--X--X--B \ \ \___/ / / \ \_______/ / \___________/ Solution: The problem is reducable to the one circle case. ___ / \ A--X---X--B \___/ There are 6 Eulerian A to B pathes for this graph. Now we can replace the central edge by a copy of this graph. This can be iterated. So we get 6*6*6 pathes for the larger graph. Problem x-free: Find an Eulerian tour which has no crossing. B---D /|\ /|\ ( A-Z-F ) \|/ \|/ C---E Solution: A symmetric solution: A-Z-B-A-C-B-D-Z-C-E-D-F-E-Z-F. Pointsymmetric solutions: Combine the symmetric points [AF], [BE], [CD] to get the graph (where each edge represents two edges in the original graph) [AF] This is the nikolaus graph again. / | \ / Z \ / / \ \ [BE]===[CD] Euch path from [AF] to Z expands to a symmetrical path in the original graph from A via Z to F. Example: AF--Z--BE--AF--CD-u-BE-d-CD--Z expands to A - Z -B - A - C - B - D \ Z F - Z - E- F- D - E - C / Problem Box: In how many ways can you make a closed string around a box such that all faces look like the four figures below? o--a---o o--a---o | | | | | | b--|+ | b---+ | | +|--a | +---a | | | | | | o---b--o o---b--o o---a--o o---a--o | | | | | | | +|--b | +---b a--|+ | a---+ | | | | | | | o--b---o o--b---o Karl Scherer once showed that you cannot do this with a closed rubber band. In all cases the rubber band was a knotted loop [Scherer]. How many essential different cases have to be considered? Which knots do appear? Which knots do we get if we allow the following crossings? o--a---o o--a---o | | | | | | | | | | | | b------b b--|---b | | | | | | o--a---o o--a---o Problem Rubik's Snake: Rubik's snake is folded as a truncated octahedron. A closer inspection shows that the problem is to find an Eulerian circle of the octahedron where no crossing is allowed (x-free). The black-white coloring of T. H. O'Beirne is the right way to find and classify them. [Gardner, Chap. 10]. References: T. van Aardenne-Ehrenfest, N. G. de Bruijn; Circuits and trees in oriented linear graphs. Simon Stevin 28 (1951) 203-217 - BEST theorem W. Ahrens; Mathematische Unterhaltungen und Spiele, Leipzig, 2. Aufl. Band II. - Kapitel XVI: Br\"ucken und Labyrinthe (bridges and mazes) 4. Geschlossene Kreise 5. Das Eulersche Br\"uckenproblem - Kapitel XX: Das Dominospiel (dominoes) 3. Ketten von 6 und von 15 Steinen (K_3, K_5) 4. Methode von G. Tarry (K_5) 5. Ketten von 28 Steinen (K_7) Aaron Bakst; Mathematical Puzzles and Pastimes, Van Nostrand, New York, 1954 - Chapter 9: One-Way Geometry Figure 31: even Nikolaus graph W. W. Rouse Ball, H. S. M. Coxeter; Mathematical Recreations and Essays, 11th edition - Chapter IX: Unicursal Problems 1. Euler's problem 2. Number of ways of describing a unicursal figure Hans Borucki; Mathematik zum Schm\"okern, Aulis Verlag, K\"oln, 1993 - p222-226: falsely claims there are 40 paths for the Nikolaus graph. Henry Ernest Dudeney; The Canterbury Puzzles, 4th ed. (reprint: Dover Publ. 1958) Problem 18: The Shipman's Puzzle - Number of Eulerian tours of a K_5 is 264 (labeled, directed) Henry Ernest Dudeney; Puzzles and Curious Problems, Thomas Nelson and Sons, Ltd., London 1931, Problem 267: A Motor-Car Tour - Number of Eulerian tours of a K_5 is 264 (labeled, directed) Problem 333: Hopscotch Puzzle (*) Henry Ernest Dudeney; Amusements in Mathematics, Thomas Nelson and Sons, London 1917, (reprint: Dover Publ. 1958, ISBN 0-486-20473-1) Problem 245: The Fly on the Octahedron - Number of Eulerian circuits of the octahedron. He counts directed routes as 1488 (which is a factor 2 to large). Leonhard Euler; Solutio problematis ad geometriam situs pertinentis, Commentarii Academiae Petropolitamae 8, 1736 (1741), 128-140 reprinted in: Opera Omnia: Series 1, Volume 7, p. 1 - 10, E53 - even degree is necessary for an Eulerian circuit. - the K\"onigsberg bridge problem. Leonhard Euler; The K\"onigsberg bridges, Scientific American, 189 (1953) 66-70 Tabor Gallai; Die K\"onigsberger Br\"ucken, die neun Fusswege und andere graphentheoretische Probleme, in: Mathematisches Mosaik, (Hrsg. Endre Hodi) Urania-Verlag, Leipzig 1977 (Matematikai Erdekessegek, Budapest 1969) - shows a solution for the Nikolaus graph (named house). 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 circle (black-white coloring by T. H. O'Beirne) K. Heinrich, H. Verrall; A construction of a perfect set of Euler tours of $K_{2k+1}$. J. Comb. Des. 5, No.3, 215-230 (1997). Zbl 914.05047 A set of $2k - 1$ Euler tours of $K_{2k + 1}$ is said to be perfect if they form a partition of the set of $(2k + 1)k(2k - 1)$ paths of length $2$ of $K_{2k + 1}$. It is shown that $K_{2k + 1}$ has such a set of perfect Euler tours. A consequence of this is that the line graph $L(K_{2k+1})$ has a Hamiltonian decomposition (the edges can be partitioned into Hamiltonian cycles). This confirms a conjecture of Kotzig. Heinrich Hemme; Das Problem des Zw\"olf-Elfs, Vandenhoeck & Ruprecht, G\"ottingen, 1998 Problem 87: Das Haus des Nikolaus - gives the upper bound 2*3*3*3 = 54 - determines the 44 paths for the Nikolaus figure Heinrich Hemme; Mensch, \"argere dich nicht, 72 Kopfn\"usse und Knobeleien f\"ur jede Gelegenheit, ro ro ro science, Hamburg, 2003, ISBN 3-499-61575-4 - p30-31, 154-155 Das Haus vom Nikolaus Jens Kamp; Danske Folkeminder, Aeventyr, Folkesagn, Gaader, Rim og Folketro, samlede fra Folkemunde, Odense 1877, p323-325 (some unicursal problems [cited by Ahrens Chap XVI]) Donald E. Knuth; The Art of Computer Programming 4, Pre-Fascicle 2c, June 2002 Section 7.2.1.3: Generating all Combinations, Excercise 106 - the number of Eulerian circuits of the complete graph K_7 Manfred Leppig; Abbildungen und topologische Strukturen, Herder Verlag, Freiburg, 1973, ISBN 3-451-16650-X - 3.3 Das K"onigsberger Br"uckenproblem, - p93-94, "Das ist das Haus vom Nikolaus" Walter Lietzmann; Lustiges und Merkw\"urdiges von Zahlen und Figuren, Vandenhoeck & Ruprecht, G\"ottingen, 1982 (11th Edition) (first edition, 1921) - Part: Von geometrischen Formen 13. Allerlei Linienz\"uge 13.1 Unikursale Figuren und \"ahnliches. K_5, K_7, figure 126 shows the Nikolaus graph (unnamed) E. Lucas; R\'ecr\'eations Math\'ematiques 4, (1894) - method of Tarry, p123-151 Brendan D. McKay, Robert W. Robinson; Asymptotic enumeration of Eulerian circuits in the complete graph, Combinatorics Probability, and Computing 7:4 (1998) 437-449 Zbl 0916.05048 http://www.cs.uga.edu/~rwr/pub.html - the number of Eulerian circuits of the complete graph K_n. A generating function formular has been found. They could compute the values upto K_21. L. Mittenzwey; Mathematische Kurzweil, Leipzig und Wien, 1880 Kap. 14 F\"ur Zeicher, Problems 269, 271 - P269: the K_5 (an edge is missing in the posed problem) (**) - P271: shows the Nikolaus figure, but didn't give the rhyme (*) J. W. Moon; Enumerating labelled trees, in: F. Harary (Ed.) Graph Theory and Theoretical Physics, (1967) Chapter 8, 261-272 Zbl 0204.24502 - Section 4: The Complexity of a Graph Heiner Mueller-Merbach; Technologie und Management 41:3 (1992) 57-58 - determines the 44 paths for the Nikolaus figure Karl-Heinz Paraquin; Denkspielebuch, Otto Maier Verlag, Ravensburg 1973, ISBN 3-473-37312-5 - Kapitel 15: Zeichenzug cover back page asks for the number or paths for the Nikolaus figure - gives the upper bound 2*3*3*3 = 54, shows the rhyme Karl-Heinz Paraquin (= Para); Denkspiele, Ravensburger Taschenbuecher 466, 1978, p2 and p112 - gives the upper bound 2*3*3*3 = 54, shows the rhyme Emanuel R\"ohrl (Editor); Graphentheory, Der Mathematikunterricht, 19:2 (March 1973) 5 - shows the rhyme: Das ist das Haus vom Nikolaus 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 Karl Scherer; Rubber Wrapper, (problem 444 of Horace W. Hinkle) Jornal of Recreational Mathematics, 12 (1979/80) 60-62 Fred. Schuh; The Master Book of Mathematical Recreations, Dover Publ. 1968, - Chapter 14.7 Road Puzzles (Sections 289-292) David Singmaster; Sources in Recreational Mathematics, An Annotated Bibliography, 7th Pre. Ed., Oct. 1999 Part II, Sect. 5.E. EULER CIRCUITS AND MAZES Jerry Slocum; The Puzzle Arcade, Klutz, 1996, ISBN 1-57054-056-X, - Hopscotch Puzzle p32, 45 (*) N. J. A. Sloane; Handbock of Integer Sequences. M2183 : What is the number of Euler circiuts in a complete graph with n vertices, when n is odd? N. J. A. Sloane & S. Plouffe; The Encyclopedia of Integer Sequences, Academic Press, (1995) http://www.research.att.com/~njas/sequences/ 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. R\"udiger Thiele; Mathematische Beweise, BGB B.G. Teubner, Leipzig, 1979 (Lizenzausgabe: Harri Deutsch Verlag Tb Nr. 25) ISBN 3-87144-495-2. - Nikolaus Graph Abb. 4.5, Problem 4.19 asks for the number of Euler paths. (no solution given) Alan Tucker; A new applicable proof of the Euler circuit theorem, American Mathematical Monthly 83, 638-640 (1976) Zbl 337.05125 H. Verrall; A construction of a perfect set of Euler tours of $K_{2k}+I$, J. Comb. Des. 6, No.3, 183-211 (1998) Zbl 911.05047 - K_2k plus a perfect matching (case k=2 is the even nikolaus graph) J. C. Wilson; On the Traversing of Geometrical Figures, Oxford, Oxford University Press, 1905 (what does this book contain?) ???; Transforming eulerian trails, Discrete Mathematics 109 (1992) 103-116 ???; Transformations of Euler tours, Annals of Discrete Mathematics 8 (1980) 65-69 Dirk Brundelius (DRUKI); Haus vom Nikolaus (solutions) http://www.druki.de/nikohaus/nikohaus.htm (german) Has animated gif-figures for all 44 solutions. J\"urgen K\"oller; http://www.mathematische-basteleien.de/ http://www.mathematische-basteleien.de/nikolaushaus.htm (german) http://www.mathematische-basteleien.de/house.html (english) Volker P\"ohl; Denksport f\"ur Besserwisser - Das Haus vom Nikolaus, http://home.t-online.de/home/volker.poehls/niko1.htm (Lists all solutions. An animated gif shows a special one.) (*) the excercise asks for only one solution. (**) it is looked for a special circuit. Draw the K_5 as a regular pentagon with all its diagonals. Color the sides black and the diagonals red. Find an alternating Eulerian circuit. Appendix: Question: In how many ways can 2n points be pairwise connected? Answer: In P(n) = (2n-1)(2n-3)(2n-5)...1 = (2n-1)!! ways. The first point can be connected with 2n-1 others. We are left with 2n-2 points. This gives P(n) = (2n-1)*P(n-1). Question: In how many ways can 2n-1 points be pairwise connected with one unconneted point? Answer: In Q(n)=(2n-1)(2n-3)(2n-5)...1 = (2n-1)!! ways. There are (2n-1) ways to select the singleton. We are left with 2n-2 points. This gives Q(n) = (2n-1)*P(n-1). Question: In how many ways can n edges be connected by n further edges to form a single circle? Answer: In R(n)=(2n-2)(2n-4)(2n-6)...2 = (2n-2)!! ways. Select an end-point. It can be connected with 2n-2 others. We are left with n-1 paths. This gives R(n) = (2n-2)*R(n-1). Boundary value: R(1) = 1. Question: How many partitions of Edges(G) into circles has an even graph G? Answer: P(degree(v1)/2) * P(degree(v2)/2) * ... * P(degree(vN)/2) with v1, v2, ... vN the vertices of G. Example: even Nikolaus graph -> 3*3*3*3 = 81 Question: How many partitions of Edges(G) into circles has an even graph G where vertex v1 is in one circle only? Answer: R(degree(v1)/2) * P(degree(v2)/2) * ... * P(degree(vN)/2) with v1, v2, ... vN the vertices of G. Example: even Nikolaus graph -> 2*3*3*3 = 54 (for each vertex) Quicky: Explain the difference of determine an upper bound for the number of Eulerian tours in the following models: - Paraquin's counting - pairwise connecting the edges at the vertices. Hint: Look at the graph A-B=C (double edge between B and C). Make the Paraquin counts for a path starting at A and one for stating at B. 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