שינוי הצבע של קשת במעגל מונוכרומטי של גרף

יהי G=(V,E) גרף פשוט מכוון שכל קשת שלו צבועה בצבע כחול או צהוב. מעגל מונוכרומטי בגרף G הינו מעגל פשוט שכל קשתותיו צבועות באותו הצבע. נתון כי ב-G יש מעגל מונוכרומטי אחד בדיוק. הוכח כי קיימת לפחות קשת אחת ב-G אשר שינוי צבעה ישאיר את הגרף ללא מעגלים מונוכרומטיים. האם הטענה נכונה גם עבור גרף לא-מכוון?

אשמח לעזרה עם השאלה הנ"ל.
תודה רבה :slight_smile:

נתון כי ב-G יש מעגל מונוכרומטי אחד בדיוק. נניח בלי הגבלת הכלליות כי מעגל זה צבוע בצבע כחול. כמו כן, נסמן מעגל זה:

X=v_{0}\to v_{1}\to...\to v_{n}\to v_{0}

נניח בשלילה, כי לא קיימת קשת בגרף G, ששינוי הצבע שלה יוביל את הגרף להיות חסר מעגלים מונוכרומטים. כלומר, לכל 0\leq i\leq n-1, שינוי הצבע של הקשת v_{i}\to v_{i+1} לצהוב, יוביל למעגל צהוב. לפיכך, נוכל להסיק כי לכל 0\leq i\leq n-1 קיים מסלול צהוב מ-v_{i+1} ועד v_{i}. אי-לכך, ניתן ליצור מסלול צהוב מ-v_{0} ל-v_{n-1} וממנו ל-v_{n-2} וכך האלה, עד v_{1} ומשם ל-v_{0}. כל הקשתות של מסלול זה צבועות בצבע הצהוב ולכן ע"פ ההגדרה מדובר במעגל מונוכרומטי המתחיל ומסתיים ב-v_{0}. כך קיבלנו שבגרף G קיימים שני מעגלים מונוכרומטים, בסתירה לכך שנתון כי G מכיל רק מעגל מונכרומטי אחד. לפיכך, קיימת קשת אחת לפחות במעגל הכחול, אשר הפיכת צבעה לצהוב, תוביל את הגרף להיות חסר מעגלים, כנדרש.

הטענה אינה נכונה עבור גרף לא מכוון. נתבונן בגרף הבא:

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