תורת הגרפים

[Bananaa6]

תורת הגרפים

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

תודה מראש לעוזרים!

 

[אורי769]

בא נראה

נניח הוכחנו לכל מספר עד k. נניח ל-G יש k+1 צביעה נאותה בה כל צבע צובע לפחות שני צמתים. עבור הצביעה הזו - נגרע מ-G את כל הצמתים הצבועים בצבע ה-k+1. נקבל גרף חדש H. לטענתי H מקיים את תנאי המשפט עבור k. מכאן תנסה להמשיך.

 

[Bananaa6]

כן אבל...

תודה, אבל מה מבטיח לך שבהסרת צבע מהצביעה הראשונה יקטין את המספר הכרומטי? ואם אני מסיר מהצביעה המינימלית מה מבטיח שאפשר לצבוע את זה בצביעה השנייה?

 

[Bananaa6]

לא לגמרי הבנתי...

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

 

[אורי769]

אתה צודק

אני לא חשבתי על זה עד הסוף. אני אחשוב על זה עוד קצת ואם יהיה לי רעיון אכתוב אותו.

 

[Bananaa6]

תודה! אשמח אם עוד אנשים ינסו לעזור

 

[Bananaa6]

אוקיי מצאתי רמז לא סגור על הסוף...

טוב אז מצאתי רמז לבעיה (מצורף בתמונה), אני עדיין לא סגור על הסוף למה חייב להיות צבע שמכיל יותר 2 קודקודים?