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

[student47]

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

א'. הוכח/הפרך: בכל גרף פשוט יש שניי קדקדים בעלי דרגה זהה.
ב'. הוכח: קיים גרף פשוט מסדר 6 שבו יש בדיוק 2 קדקדים עם דרגה זהה, ולא יותר.

הוכחה של א':

יהא G גרף פשוט מסדר n.
הדרגה המקסימלית של קדקד (v in V(G היא n-1.
הדרגה המינימלית של קדקד (u in V(G היא 0.

לכן לכל קדקד ב-G יכולה להיות אחת מ-n דרגות אפשריות: zz 0,1,2,...,n-1 zz .
נניח בשלילה שאין 2 קדקדים בעלי דרגה זהה.
לכן קיים קדקד v in V(G) שדרגתו היא n-1, וקיים קדקד w in V(G) שדרגתו היא 0.
לכן zz (u,v) in E(G) zz.
סתירה לכך שהדרגה של u היא 0 ולכן לא יתכן שחלה בו צלע.
הנחת השלילה מובילה לסתירה ולכן יש שניי קדקדים בעלי דרגה זהה.

האם ההוכחה הזו מדוייקת?

את סעיף ב' אני לא ממש מצליח.

תודה רבה לעונים!

 

[טרול המתכנן]

הטענה שגויה, ההוכחה בסדר.

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

ב׳: החלוקה חייבת להיות 0-1-2-2-3-4, שחק עם זה קצת, לא מסובך.

 

[student47]

בקשר לתגובה שלך על סעיף ב'

לא ממש הבנתי למה אתה מתכוון כשאמרת שהחלוקה צריכה להיות 0-1-2-2-3-4 .
הכוונה שיש 6 קדקדים שדרגתו של אחד היא 0, שני 1, שלישי 2, רביעי 2, חמישי 3, שישי 4?

כלומר לנסות לבנות ממש גרף פשוט עם הדרגות הללו?

 

[אורי769]

כמה הערות

ראשית, גם חלוקה 5-4-3-3-2-1 אפשרית (המשלים לדוגמא 0-1-2-2-3-4). שנית, אני מסכים שזה לא מסובך לבנות דוגמא כזו. אבל מה שיותר מעניין מתמטית זה להראות קיומה של דוגמא לכל n . כלומר דוגמא לגרף על n קודקודים שהדרגות כולן דונות פרט לזוג בודד. ניתן לבנות דוגמא כזו באופן רקורסיבי כך שבכל שלב מגדירים למי הקודקוד הנוסף יחובר. אם תרצה אראה את הבניה.