כמה דברים לגבי הוכחת משפט בתורת הגרפים
http://math-wiki.com/images/2/24/GT.L10.pdf
אני מדבר על המשפט בעמוד 1 (משפט 2).
ההוכחה מסתיימת באמצע עמוד 2.
בסיום טענת עזר 2, כתוב "המשך הוכחת המשפט". זה החלק שבו יש כמה דברים שלא ברורים לי.
בחלק הזה, כתוב שיש שידוך מושלם מ-V1 ל-V2.
שאלה 1:
יש נקודה שאני רוצה להיות בטוח לגביה..יש לי את הגרף G, ועל גביו מגדירים שידוך מושלם - כלומר בין כל 2 קדקדים בשידוך, קיימת צלע בגרף, אבל יתכן שיש צלע בין 2 קדקדים בגרף, שאינה נמצאת בשידוך?
שאלה 2:
כתוב "לפי ההגדרות, לכל 2 צלעות בשידוך אין קדקד משותף". ההגדרות שעליהן מדובר הן ההגדרה של גרף דו"צ וההגדרה של שידוך מושלם?
שאלה 3:
לא ברור לי החלק שכתוב "נצבע את צלעות השידוך המושלם של G בצבע d, ונשמיט אותך מהגרף".
מה הכוונה לצבוע בצבע d?
ולמה צובעים אותן בכלל?
שאלה 4: למה בסוף, מכך שמקבלים גרף 0 רגולרי, מסתיימת ההוכחה? ההוכחה אמורה להסתיים כשמוכיחים ש-i(G)<=d .
תודה רבה לעונים ושנה טובה.
http://math-wiki.com/images/2/24/GT.L10.pdf
אני מדבר על המשפט בעמוד 1 (משפט 2).
ההוכחה מסתיימת באמצע עמוד 2.
בסיום טענת עזר 2, כתוב "המשך הוכחת המשפט". זה החלק שבו יש כמה דברים שלא ברורים לי.
בחלק הזה, כתוב שיש שידוך מושלם מ-V1 ל-V2.
שאלה 1:
יש נקודה שאני רוצה להיות בטוח לגביה..יש לי את הגרף G, ועל גביו מגדירים שידוך מושלם - כלומר בין כל 2 קדקדים בשידוך, קיימת צלע בגרף, אבל יתכן שיש צלע בין 2 קדקדים בגרף, שאינה נמצאת בשידוך?
שאלה 2:
כתוב "לפי ההגדרות, לכל 2 צלעות בשידוך אין קדקד משותף". ההגדרות שעליהן מדובר הן ההגדרה של גרף דו"צ וההגדרה של שידוך מושלם?
שאלה 3:
לא ברור לי החלק שכתוב "נצבע את צלעות השידוך המושלם של G בצבע d, ונשמיט אותך מהגרף".
מה הכוונה לצבוע בצבע d?
ולמה צובעים אותן בכלל?
שאלה 4: למה בסוף, מכך שמקבלים גרף 0 רגולרי, מסתיימת ההוכחה? ההוכחה אמורה להסתיים כשמוכיחים ש-i(G)<=d .
תודה רבה לעונים ושנה טובה.