להראות בעזרת משפט ארדש-סקרש שיש k-צביעה בגרף

מתמטיקה
,
1

שלום לכולם, אשמח לעזרה עם השאלה הבאה:

יהי G גרף לא מכוון ללא משולשים על n צמתים, כאשר n\geq 55. הראו שקיים מספר שלם חיובי k כך שיש k-צביעה של G, שצובעת 10 צמתים באותו הצבע.

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

2

למען הסדר הטוב, נספק את ההגדרה הבאה: R=R(s,t) הוא המספר הטבעי הקטן ביותר כך שבכל צביעה של צלעות הגרף K_R בשני צבעים (אדום וכחול), קיים תת-גרף שלם K_s שצבוע בכחול או שקיים תת-גרף שלם K_t שצבוע באדום.

משפט ארדש-סקרש:

R(s,t)\leq {s+t-2\choose s-1}

כעת נוכיח את הטענה המבוקשת. ע"פ משפט ארדש-סקרש מתקיים:

R(3,10)\leq {3+10-2\choose 3-1}={11\choose 2}=55

כמו כן, נתון כי n\geq 55. לכן בכל צביעה של צלעות K_n בכחול ואדום חייב להיות משולש כחול או K_{10} אדום. בפרט, זה המקרה אם נצבע את צלעות G בכחול ואת הצלעות של \bar{G} באדום. ההנחה שאין משולשים בגרף G גוררת שיש תת-גרף \bar{G} איזומורפי ל-K_{10}. הקדקודים של תת-הגרף הזה מהווים קבוצה בלתי-תלויה בגרף G כלומר אין שניים מהם שמחוברים ע"י צלע. לכן אפשר לצבוע את כל העשרה באותו צבע באופן חוקי.
מקווה שמובן, בהצלחה.