שינויים
'''פתרון''': נבחר <math>v_0\in V</math> ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ <math>v\to u</math> הצעד הבא לא יהיה <math>u\to v</math> (זה אפשרי כי כל קדקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קדקודים נקבל חזרה על קדקוד כלשהו בשלב כלשהו. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!
==תרגיל==
יהי <math>G=(V,E)</math> גרף, ונסמן <math>\delta_G=\underset{v\in V}{\min}\{deg(V)\}</math> את הדרגה המינימלית בגרף. נניח <math>\delta_G\geq 1</math>. הוכיחו:
א. יש בגרף מסלול פשוט מאורך לפחות <math>\delta_G</math>.
ב. יש בגרף מעגל פשוט מאורך לפחות <math>\delta_G+1</math>.
===פתרון===
א. יהי <math>(v_1,v_2,\dots ,v_k)</math> מסלול פשוט מאורך מקסימלי. מתקיים: <math>\deg(v_1)\geq \delta_G</math>. טענה: כל שכניו נמצאים במסלול. הוכחה: אחרת אפשר להוסיף שכן שלא במסלול לתחילת המסלול ולקבל מסלול פשוט ארוך יותר בסתירה למקסימליות. לכן אורך המסלול לפחות כמו <math>\delta_G</math>.
ב. יהי <math>(v_1,v_2,\dots ,v_k)</math> מסלול פשוט מאורך מקסימלי. ראינו שכל שכני הראשון במסלול, ולכן מספיק לקחת את המסלול עד שמגיעים לאחרון השכנים, ואז לחזור חזרה ל <math>v_1</math> ולקבל מעגל פשוט מהאורך המתאים.
==תרגיל==
נניח כי הם שונים, אזי ב<math>|[v]|,|[u]|\geq 51</math> ( הקודוקד + לפחות 50 שכנים). אלו הם שני מרכיבי קשירות שונים ולכן הם זרים, ומכך שבגרף יש לכל הפחות 102 קדקודים, סתירה.
'''הערה:''' אפשר להכליל את התרגיל, ולהפוך אותו לתרגיל על קוטר של גרף: יהי <math>G=(V,E)</math> גרף עם <math>|V|=n</math>. הוכיחו שאם דרגת כל קודקוד היא לפחות <math>\frac{n-1}{2}</math> אז <math>diam(G)\leq 2</math>, ובפרט <math>G</math> קשיר.
הוכחה: יהיו <math>v,u\in V</math>. אם הם שכנים אז <math>d(v,u)=1</math>. אם לא, אז נניח בשלילה שאין להם שכן משותף ונקבל ש- <math>\Gamma(v)\cap \Gamma(u)=\varnothing</math>, ובנוסף <math>|\Gamma(v)|,|\Gamma(u)|\geq \frac{n-1}{2}+1</math>, ולכן יש בגרף לפחות <math>|\Gamma(v)\cup \Gamma(u)\cup \{v,u\}|=2\cdot \frac{n-1}{2}+2=n+1</math> קודקודים (צריך לקחת את הערך השלם של החצינובע מכך שהאיחוד זר) בסתירה. לכן יש להם שכן משותף ולכן <math>d(v,u)=2</math>. בסה"כ נקבל <math>\forall v,u:d(v,u)\leq 2</math> ולכן <math>diam(G)\leq 2</math>.
==תרגיל==
==תרגיל==
יהא <math>G=(V,E)</math> גרף פשוט סופי לא מכוון. נניח כי <math>V=V_1\cup V_2</math> איחוד זר (כלומר החיתוך <math>V_1\cap V_2=\emptyset</math>. עוד נניח כי קיים <math>v_i\in V_i</math> כך שקיימת קשת <math>(v_1,v_2)\in E</math> והיא הקשת היחידה בין <math>V_1</math> ל <math>V_2</math>.
הוכיחו שקיים קודקוד בעל דרגה אי זוגית.
פתרון: נסתכל על תת הגרף <math>V_1</math> אם <math>v_1</math> בעל דרגה זוגית בו אז הוא יהיה בעל דרגה אי זוגית ב V. אחרת דרגתו ב V1 אי זוגית ולכן לפי משפט לחיצת היחדים הידיים שסכום הדרגות זוגיות, קיים עוד קודוד בעל דרגה אי זוגית ב V1. כיון כיוון שהקשת היחידה בין <math>V_1</math> ל <math>V_2</math> היא <math>(v_1,v_2)\in E</math> נקבל כי קודקוד זה בעל דרגה אי זוגית גם ב G.
==תרגיל==
