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

במסיבה כלשהי יש אנשים; חלקם לחץ ידיים זה עם זה. אנא הוכח שמספר האנשים שלחצו ידיים עם מספר אי-זוגי של אנשים - הוא זוגי.



דוגמה:

נניח שבמסיבה יש שלשה אנשים: 1,‏ 2,‏ ו3, ורק 1 ו2 לחצו ידיים זה עם זה. יש שני אנשים שלחצו ידיים עם אדם אחד; אכן יש מספר זוגי (שניים) של אנשים שלחצו ידיים עם מספר אי-זוגי (אחת) של אנשים.



רמז

צייר גרף שבו כל אדם הוא צומת. מה יקרה אם תמחק צומת כלשהו והקשתות היוצאות ממנו?