שאלות ממבחן בתורת הגרפים

[Lucifer LightBringer]

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

השאלה הראשונה שהיא 2 במבחן היא :"יהי G גרף קשיר עם מעגלים. הוכח כי מכיל מעגל באורך לכל היותר 2diam(G)+1 ftar diam(G) הינו המרחק המירבי בצלעות בין זוג קודקודי G.
"

מצ"ב הניסיון לפיתרון.
מיותר לציין שנכשלתי, טוב קומבינטוריקה ותורת הגרפים תמיד היה נקודת תורפה שלי...

 

[עריסטו]

Every graph G containing a cycle satisfies g(G)≤2d+1.

Proof: Let C be a shortest cycle in G. If g(G)≥ 2diam(G) + 2, then C has two vertices whose distance in C is at least diam(G)+1. Question: why is it at least diam(G)+1? cont. of proof: In G, these

math.stackexchange.com

 

[Lucifer LightBringer]

עוד שתי שאלות נוספות:
1. הראה שכל צביעה של הצלעות בגרף השלם K_n על n>=3 באדום וכחול מכילה מעגל המילטון המורכב משני מסלולים מונוכרומטיים.
2. יהיה k שלם חיובי ו-G=(AUB,E) גרף דו צדדי עם זיווג מושלם שבו דרגתו של כל קודקוד בצד A היא לפחות k. הראה ש-G מכיל לפחות k! זיווגים מושלמים. (הסימן קריאה ב-k זה עצרת).
מצ"ב הפתרונות שלי במבחן דאז.

אני בטוח שזה מופיע איפשהוא בספרות בתורת הגרפים.