חידת גרפים

[עריסטו]

חידת גרפים

בגרף מישורי פשוט בעל n קדקודים ו - 3n-6 קשתות יש שני קדקודים בעלי דרגה אי-זוגית, ודרגת שאר הקדקודים היא זוגית. האם ייתכן ששני הקדקודים בעלי הדרגה האי-זוגית הם שכנים?

 

[הפרבולה]

תשובה

לא יתכן. הוכחה:
בגרף שמקיים 3n-6 קשתות כל הפאות הם "משולשים" ( במובן שפאה תחומה על ידי 3 קשתות).
נניח שבגרף כזה יש רק 2 קודקודים איזוגיים והם שכנים.
נסמן את הקודקוד הראשון האיזוגי ב A ויש לו קשתות ל K שכנים B1 B2 B3 ....BK כאשר K אי זוגי ו B1 דרגה אי זוגית ושאר הקודוקדים B2...BK דרגה זוגית וגם הם שכנים במעגל כלומר B1 שכן של B2 ששכן ל B3 ששכן ל .... עד חזרה ל B1 ( נובע מזה שכל הפאות משולים)
אז A וB1 הם שכנים ואיזוגיים וכל שאר הקודוקדים ( כולל B2...BK) זוגיים.

נסלק את הנקודה A מהגרף ואת K הקשתות שמתחברים אליה.
הקודקוד B1 הפך להיות זוגי והקודקדים B2...BK לאיזוגיים.
נחבר את B2 ב K-3 קשתות ל B4 B5....BK , כעת B2 נשאר בדרגה איזוגית (כי הוספנו לו K-3 קשתות ו K-3 אי זוגי כי K אי זוגי ), גם B3 נשאר אי זוגי ( לא חיברנו אליו קשת מ B2 כי הוא כבר שכן שלו )

קיבלנו גרף חדש עם n-1 קודקודים שמקיים שמספר הקשתות הוא 3 כפול n-1 פחות 6 ( כלומר שוב גרף מישורי שכל פאותיו משולשים ) שיש בו 2 קודקודים אי זוגיים שכנים B2 B3.

נחזור על התהליך שוב ושוב ונקבל כל פעם גרף מישורי עם מספר קודקודים פחות 1 מהקודם שכל פאותיו משולשים ויש בו 2 קודוקדים שכנים אי זוגיים , אבל זה לא יתכן כי שנגיע ל n=2 כל הקודקודים הם בדרגה זוגיית .

 

[הפרבולה]

תיקון קטן

צריך להיות
(כי הוספנו לו K-3 קשתות ו K-3 זוגי כי K אי זוגי )

ובנוסף:
בשלב הסופי נגיד ל n=3 שכל קודקדיו דרגה אי זוגית

 

[עריסטו]

פתרון נוסף

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