שאלה בתורת הגרפים.
הראה שלגרף פשוט עם n>=7 קודקודים ולפחות 5n - 14 קשתות יש תת גרף עם דרגה מינימלית 6. הצבתי מספרים קטנים ורואים שזה יוצא, אבל אני לא מצליח לנמק מדוע. נניח עבור n=10, אז יש לפחות 36 קשתות ולכן סכום כל הדרגות הוא לפחות 72. כעת צריך לחלק את הדרגות בין עשרת הקודקודים. אם משחקים קצת עם המספרים רואים שכאשר מקטינים את דרגתם של חלק מהקודקודים שתהיה קטנה מ6 מקבלים שיש מספיק קודקדים עם דרגה מספיק גבוהה כך שזה "לא משנה" שדרגתם של שאר הקודקודים קטנה מ6, אבל אלו רק נפנופי ידים... מישהו יכול לתת לי כיוון לנימוק שבאמת מסביר מדוע זה הטענה מתקיימת עבור n=10 (אני מקווה שאח"כ אני אוכל להתמודד לבד עם המקרה הכללי)? תודה מראש.
הראה שלגרף פשוט עם n>=7 קודקודים ולפחות 5n - 14 קשתות יש תת גרף עם דרגה מינימלית 6. הצבתי מספרים קטנים ורואים שזה יוצא, אבל אני לא מצליח לנמק מדוע. נניח עבור n=10, אז יש לפחות 36 קשתות ולכן סכום כל הדרגות הוא לפחות 72. כעת צריך לחלק את הדרגות בין עשרת הקודקודים. אם משחקים קצת עם המספרים רואים שכאשר מקטינים את דרגתם של חלק מהקודקודים שתהיה קטנה מ6 מקבלים שיש מספיק קודקדים עם דרגה מספיק גבוהה כך שזה "לא משנה" שדרגתם של שאר הקודקודים קטנה מ6, אבל אלו רק נפנופי ידים... מישהו יכול לתת לי כיוון לנימוק שבאמת מסביר מדוע זה הטענה מתקיימת עבור n=10 (אני מקווה שאח"כ אני אוכל להתמודד לבד עם המקרה הכללי)? תודה מראש.