שינויים
/* תרגילים נוספים */
'''תרגיל''': יהי <math>G</math> גרף מסדר <math>n>1</math>. הוכח שקיימים 2 קדקודים בעלי אותה דרגה.
'''פתרון:''' נביט בפונקציית הדרגה <math>\operatorname{deg}:V \to \{0,1,\dots,n-1\}</math> השולחת כל איבר אל הדרגה שלו: <math>v\mapsto \operatorname{deg}(v)</math>; כדי להבין את התמונה של הפונקציה, נשים לב שיש שני מקרים:
#אם קיים קדקוד מדרגה <math>n-1</math>, אז הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה מתקיים
<math>\operatorname{Im}(f) \subseteq \{1,\dots n-1\} </math>.
#אם אין קדקוד מדרגה <math>n-1</math> אז<math>\operatorname{Im}(f) \subseteq \{0,1,\dots n-2\} </math>.
בשני המקרים קיבלנו כי <math>|\operatorname{dom}(f)|=|V|=n, |\operatorname{Im}(f)|\le n-1</math> ולכן <math>f</math> אינה חח"ע.
'''תרגיל''': יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי <math>G</math> קשיר.
'''פתרון''': יהיו <math>v,u\in V</math> . צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).נניח כי הם שונים , אזי ב<math>|[v]|,|[u]|\geq 50</math> והם זרים. לכן אלו הם שני מרכיבי קשירות שונים ולכן הם זרים, ומכך שבגרף יש לכל היותר 100 קדקודים, בהכרח <math>|[v]|=|[u]|=50</math> אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49. , סתירה.
'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math>. הוכח כי אם נניח כ בגרף מתקיים <math>\forall v\in V : \textoperatorname{degreedegre}(v)\geq 2</math> אז בגרף יש מעגל.
'''פתרון''': בגרף יש יותר מ 2 קדקודים (אחרת לא יהיה יהיו להם 2 שכנים).לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\textoperatorname{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>, ולכן מספר הצלעות גדול שווה ממספר הקדקודים. לפי משפט קודם קיים מעגל בגרף.
'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> גרף ללא מעגלים עם <math>|V|\geq 2</math>. הוכח כי קיימים <math>v_1,v_2\in V</math> כך שדרגתם לכל היותר 1.
'''פתרון''': לפי תרגיל קודם קיים <math>v\in V</math> כך שדרגתו לכל היותר 1 (אחרת לכל הקדקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם. סתירה!).
נמשיך באינדוקציה על <math>n</math> מספר הקדקודים בגרף.
אם <math>n=2</math> אזי או שהגרף הוא 2 נקודות לא ללא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 2 הנקודות של הגרף הם הן מדרגה קטנה שווה ל-1.
כעת נניח כי הטענה נכונה עבור <math>n\geq 2</math>. נוכיח את הטענה עבור <math>n+1</math>.
נבחר את הקדקוד <math>v\in V</math> שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל (אם קיימת), ונקבל גרף עם <math>n</math> קדקודים. לפי הנחת האינדוקציה יש בו 2 קדקודים<math>v_1,v_2</math> בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את <math>v</math> שהשמטנו). יש מספר מקרים:# אם <math>v</math> שכן של <math>v_1</math> אזי <math>v,v_2</math> בעלי דרגה לכל היותר 1. # אם <math>v</math> שכן של <math>v_2</math> אזי <math>v,v_1</math> בעלי דרגה לכל היותר 1. # אם <math>v</math> שכן של <math>v_1,v_2</math> - סתירה כי הדרגה של <math>v</math> היא 1 לכל היותר.# אם <math>v</math> לא שכן של <math>v_1,v_2</math> אזי <math>v,v_1,v_2</math> בעלי דרגה לכל היותר 1.
