מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/גרפים וייצוגיהם/תרגילים/לחיצת ידיים במסיבה/תשובה

נוכיח את הטענה באינדוקציה על $\displaystyle n$, מספר הצמתים.

(בסיס האינדוקציה) אם בגרף יש צומת יחיד, אין קשתות. אם בגרף יש שני צמתים, אז או שיש קשת אחת, או שאין אף קשת. בכל אחד ממקרים אלה, בדיקה פשוטה מראה שהטענה מתקיימת. לכן הטענה נכונה עבור $\displaystyle n=1,2$.

(מעבר האינדוקציה) נניח שהטענה נכונה עבור כל גרף בעל $\displaystyle n-1$ צמתים, ונראה שהטענה נכונה עבור כל גרף בעל $\displaystyle n$ צמתים. ניקח גרף בעל $\displaystyle n$ צמתים, ונחפש צומת $\displaystyle u$ שמספר שכניו אי-זוגי. (אם אין צומת כזה, הטענה בהכרח נכונה לגרף זה.) נניח ששכניו של $\displaystyle u$ הם $\displaystyle u_{1},\ldots ,u_{i}$. נשים לב ש$\displaystyle i$ בהכרח אי-זוגי. אם נמחק את $\displaystyle u$ והקשתות שיוצאות ממנו, הטענה נכונה מהנחת האינדוקציה. לאחר הוספת $\displaystyle u$ מחדש, כמה צמתים בעלי דרגה אי-זוגית נוצרו? $\displaystyle u$ עצמו תורם 1. כל שכן של $\displaystyle u$ בעל דרגה זוגית הופך להיות בעל דרגה אי-זוגית, וכל שכן של $\displaystyle u$ בעל דרגה אי-זוגית הופך להיות בעל דרגה זוגית. היות ש$\displaystyle i$ אי-זוגי, תרומת שכניו היא מספר אי-זוגי (חיובי או שלילי). לכן נוצר עוד מספר זוגי (חיובי או שלילי) של צמתים בעלי דרגה זוגית.

דוגמה: בתרשים הבא, יש ל$\displaystyle u$‏ 3 שכנים: 2 בעלי דרגה אי-זוגית (בלעדיו), ו1 בעל דרגה זוגית (בלעדיו). דוגמה להוכחת משפט "לחיצת הידיים". לאחר הוספת $\displaystyle u$, יש ל$\displaystyle u$‏ 2 שכנים בעלי דרגה אי-זוגית (יחד אתו), ושכן יחיד בעל דרגה זוגית (יחד אתו). הוספת $\displaystyle u$ ייצרה עוד 0 צמתים בעלי דרגה אי-זוגית: $\displaystyle u$ עצמו בעל דרגה אי-זוגית, $\displaystyle u_{1}$ הפך להיות בעל דרגה זוגית, $\displaystyle u_{2}$ הפך להיות בעל דרגה אי-זוגית ו$\displaystyle u_{3}$ הפך להיות בעל דרגה זוגית.