הצגת המקור של הדף "למת לחיצות הידיים"

[[קובץ:6n-graf.svg|ממוזער|250px|בגרף יש מספר זוגי של צמתים (הצמתים 2, 4, 5, 6) בעלי דרגה אי זוגית. וסכום הדרגות של הצמתים הוא 14=2+3+2+3+3+1 שהוא פעמיים מספר הקשתות]]
'''למת לחיצות הידיים''' קובעת כי במסיבה שבה חלק מהאנשים לוחצים ידיים, כמות האנשים שלחצו ידיים מספר [[אי זוגי]] של פעמים חייבת להיות [[מספר זוגי|זוגי]]ת. ללמה שימושים ב[[תורת הגרפים]], וממנה נובע כי בכל [[גרף לא מכוון]] קיימים מספר זוגי של צמתים ש[[דרגה (תורת הגרפים)|דרגתם]] אי זוגית. הלמה היא תוצאה של '''נוסחת סכום הדרגות''' (נקראת גם: '''משפט הדרגה''' או '''משפט הדרגות''') לפיה לכל גרף <math>G</math> מתקיים: <math>\sum_{v\in V}deg(v)=2|E|</math>{{הערה|1=<math>E</math> מציין את מספר הקשתות, <math>V</math> מציין מספר הצמתים של <math>G</math> ו-<math>deg(v)</math> מציין את הדרגה של הצומת <math>v</math>}}. שתי התוצאות אלו הוכחו על ידי [[לאונרד אוילר]] במאמרו על [[בעיית הגשרים של קניגסברג]] שהיווה את הבסיס לתורת הגרפים.

הצמתים בעלי דרגה אי זוגית נקראים לפעמים '''צמתים אי זוגיים''' או '''קודקודים אי זוגיים''', ולפי המינוח הזה נוכל לומר שהלמה קובעת שבכל גרף לא מכוון יש מספר זוגי של צמתים אי זוגיים.

== הוכחה ==
נוכיח קודם את נוסחת סכום הדרגות ובאמצעותה נוכיח את הלמה:

נספור בשתי דרכים שונות את מספר הזוגות <math>(v,e)</math> כאשר <math>e</math> מסמל קשת ו-<math>v</math> הוא צומת ש-<math>e</math> יוצאת ממנו, כל צומת <math>v</math> נמצא ב-<math>deg(v)</math> זוגות (שכן יוצאות מהצומת <math>deg(v)</math> קשתות), לכן מספר הזוגות הוא סכום כל דרגות הצמתים בגרף. אולם, ניתן לספור גם לפי הקשתות, כל קשת <math>e</math> נמצאת ב-2 זוגות (עם כל אחד מהקצוות של <math>e</math>), ולכן מספר הזוגות הוא גם פעמיים מספר הקשתות. כלומר קיבלנו את השוויון <math>\sum_{v\in V}deg(v)=2|E|</math>.

נוכיח באמצעות השוויון הקודם את הלמה:

נניח בשלילה שיש מספר אי זוגי <math>k</math> של צמתים אי זוגיים בגרף לא מכוון כלשהו, סכום כל הדרגות של הצמתים האי זוגיים הוא אי זוגי (כיוון שחיברנו מספרים אי זוגיים מספר אי זוגי של פעמים), סכום הדרגות של הצמתים בעלי דרגה זוגית הוא זוגי (חיבור מספרים זוגיים תמיד יוצא מספר זוגי). לכן <math>\sum_{v\in V}deg(v)</math> הוא מספר אי זוגי (כחיבור של מספר זוגי ומספר אי זוגי). אבל מתקיים <math>\sum_{v\in V}deg(v)=2|E|</math>. בסתירה לכך שצד שמאל של השוויון הוא אי זוגי, ולכן מספר הצמתים האי זוגיים בכל גרף לא מכוון הוא זוגי.

== גרפים רגולריים ==
מנוסחת סכום הדרגות נקבל שלכל [[גרף רגולרי|גרף <math>r</math>-רגולרי]] בעל <math>n</math> צמתים יש <math>nr/2</math> קשתות<ref>{{citation|title=Graphs and Applications: an Introductory Approach|series=Undergraduate Mathematics Series, The Open University|first1=Joan M.|last1=Aldous|first2=Robin J.|last2=Wilson|publisher=Springer-Verlag|year=2000|isbn=978-1-85233-259-4|page=[https://archive.org/details/graphsapplicatio0000aldo/page/44 44]|chapter=Theorem 2.2|url=https://archive.org/details/graphsapplicatio0000aldo/page/44}}</ref>. אם <math>r</math> אי זוגי, מספר הקשתות בגרף חייב להתחלק ב-<math>r</math>. כלומר, אם <math>r</math> אי זוגי בגרף יש מספר זוגי של צמתים.

== גרפים אינסופיים ==
[[קובץ:Infinite graph one direction.svg|ממוזער|גרף אינסופי שלא מקיים את למת לחיצת הידיים]]
הלמה אינה נכונה בעבור גרפים אינסופיים, וזאת גם אם בגרף ישנם רק מספר סופי של צמתים בעלי דרגה אי זוגית. לדוגמה, לגרף [[שרוך (תורת הגרפים)|שרוך]] עם נקודת קצה אחת יש רק צומת יחיד עם דרגה אי זוגית, בניגוד ללמה.
== הערות שוליים ==
{{הערות שוליים}}

[[קטגוריה:תורת הגרפים]]
[[קטגוריה:למות|לחיצות]]