Handshake Lemma: In jedem Graph ist die Anzahl der Ecken ungeraden Grades eine gerade Zahl. (Oder: Die Anzahl der Gäste auf einer Geburtstagsfeier, die ungerade vielen anderen Gästen zur Begrüssung die Hand gegeben haben, ist immer gerade - auf jeder endlichen Party.) References: W. Ahrens; Mathematische Unterhaltungen und Spiele, B. G. Teubner Verlag, Leipzig, 1901, - Chapter XVI: Einiges aus der Analysis situs - Section XVI.1: Liniensysteme Die Anazahl der Punkte ungerader Ordnung ist gerade. - Section XVI.3: Einiges aus der Morphologie der Polyeder Satz V [Legendre]: Die Ecken, von welchen eine ungerade Anzahl von Kanten ausgeht, sind stets in gerader Anzahl an einem Polyeder vertreten. Die Anzahl der Seitenflächen von ungerader Seitenzahl ist stets eine gerade. W. W. Rouse Ball, H. S. M. Coxeter; Mathematical Recreations and Essays, 11th edition - Chapter IX: Unicursal Problems 1. Euler's problem First [Euler]: The number of odd nodes in any network is even. Reinhard Diestel; Graphentheorie, 2. Auflage, Springer-Verlag, Heidelberg, 2000 ISBN 3-540-67656-2 http://www.math.uni-hamburg.de/home/diestel/books/graphentheorie/ - Proposition 0.2.1. Die Anzahl der Ecken ungeraden Grades in G ist stets gerade. Reinhard Diestel; Graph Theory, Second Edition, Springer-Verlag, New York, 2000 Graduate Texts in Mathematics, Volume 173 ISBN 0-387-98976-5 http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ E. B. Dynkin, W. A. Uspenski; Mathematische Unterhaltungen, Aulis Verlag Deubner & Co KG, Köln 1979 ISBN 3-7614-0417-4 A. Aufgaben über das Mehrfarbenproblem - Aufgabe 12: Jeder Mensch, der je gelebt hat, hat in seinem Leben eine bestimmte Zahl Händedrucke gewechselt. Man beweise, dass die Anzahl der Menschen, bei denen die Anzahl der Händedrucke eine ungerade Zahl ist, gerade ist. Arthur Engel; Problem-solving strategies, Problem Books in Mathematics. New York, NY: Springer. x, 403 p. (1998) ISBN 0-387-98219-1 Zbl 887.00002 - Chapter 1: The Invariance Principle - Problem 32: Many handshakes are exchanged at a big international congress. We call a person an odd person if he has exchanged an odd number of handshakes. Otherwise he will be called even. Show that, at any moment, there is an even number of odd persons. Leonhard Euler; Solutio problematis ad geometriam situs pertinentis, Commentarii Academiae Petropolitamae 8, 1736 (1741), 128-140. Opera Omnia Series 1-7 (1766) 1-10. Leonhard Euler; The Königsberg bridges, Scientific American, 189 (1953) 66-70 Tabor Gallai; Die Königsberger Brücken, die neun Fusswege und andere graphentheoretische Probleme, in: Mathematisches Mosaik, (Hrsg. Endre Hodi) Urania-Verlag, Leipzig 1977 (Matematikai Erdekessegek, Budapest 1969) p124: In jedem endlichen Graphen ist die Anzahl der ungeraden Punkte gerade. Martin Gardner; The Second Scientific American Book of Mathematical Puzzles and Diversions, Simon & Schuster (1961) - Chapter 5: Nine Problems - Problem 8: Handshakes and Networks Prove that at a recent convention of biophysicists the number of scientists in attendence who shook hans an odd number of times is even. The same problem can be expressed graphically as follows. Put as many dos (biophysicists) as you wish on a sheet of paper. Draw as many lines (handshakes) as you wish from any dot to any other dot. A dot can 'shake hands' as often as you please, or not at all. Prove that the number of dots with an odd number of lines joining them is even. Frank Harary; Graphentheorie, R. Oldenbourg Verlag, München Wien, 1974, ISBN 3-486-34191-X - Section 2.3: Der Grad Korollar 2.1(a): In jedem Graphen ist die Anzahl der Ecken ungeraden Grades gerade. Heinrich Hemme; Mathematik zum Frühstück, Vandenhoeck & Ruprecht, Göttingen, 1990 - Problem 58: Die Händedrücke p31, 85-86 Legendre; Elements de geometie, Laszlo Lovasz; Cobinatorial Problems and Exercises, 2nd. Edition, 1993 Laszlo Lovasz, Katalin L. Vesztergombi, Jozsef Pelikan; Kombinatorik, B. G. Teubner Verlagsgesellschaft, Leipzig, 1977, Mathematische Schülerbücherei Band 90 - Chapter 4: Kombinatorik in der Geometrie p65: Satz: In jedem Graphen gibt es geradzahlig viele Punkte ungerader Valenz. p64: In einem Graphen mit ungeradzahlig vielen Knotenpunkten ist die Anzahl der Punkte gerader Valenz ungerade. p62: In einer aus ungradzahlig vielen Menschen bestehenden Gesellschaft gibt es stets einem Menschen, der geradzahlig viele Bekannte in der Gesellschaft hat. L. Lovasz, J. Pelikan, K. Vesztergombi; Discrete Mathematics: Elementary and Beyond, Undergraduate Texts in Mathematics. Springer-Verlag, 2003, ISBN 0-387-95585-2. J. Matousek, J. Nesetril; Diskrete Mathematik: eine Entdeckungsreise, Springer Verlag, Berlin, 2002 ISBN 3-540-42386-9 - 3.3.2 : Handshake Lemma In jedem Graph ist die Anzahl der Ecken ungeraden Grades eine gerade Zahl. (Oder: Die Anzahl der Gäste auf einer Geburtstagsfeier, die ungerade vielen anderen Gästen zur Begrüssung die Hand gegeben haben, ist immer gerade - auf jeder endlichen Party.) Horst Sachs; Einführung in die Theorie der endliche Graphen, Teil 1, B. G. Teubner Verlagsgesellschaft, Leipzig, 1970 - Chapter 2: Eulersche und Hamiltonische Linien - Problem 2.2.1: Die Anzahl der Knotenpunkte ungerader Valenz eines beliebigen Graphen ist gerade. Rüdiger Thiele; Mathematische Beweise, Deutsch Taschenbücher Band 25, Harri Deutsch Verlag, 1979 ISBN 3-87144-495-2 - Section 5.2: Unmöglichkeitsbeweise - Problem 5.4: Es ist unmöglich, dass sich bei einer Begrüssung 7 Personen die Hände geben, und zwar so, dass jeder genau zwei Personen nicht die Hand gegeben hat. (Jede Person soll 5 andere begrüssen!) -- mailto:Torsten.Sillke@uni-bielefeld.de http://www.mathematik.uni-bielefeld.de/~sillke/