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

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



דוגמה:

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