שינויים
/* תרגילים נוספים */ דרגה שווה
=תרגילים נוספים=
'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> גרף בעל <math>3\leq n\ge 3</math> קדקודים.אם בגרף ו-<math>n\leq m \ge n </math> צלעות . אזי בגרף יש מעגל.
'''פתרון''': באינדוקציה.
עבור <math>n=3</math> אזי יש מדובר במשולש הגרף הוא בהכרח משולש (לא יכול יכולות להיות יותר מ -4 צלעות ב-עבור 3 קדקודים) ואכן מתקיים כי יש מעגל.
נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>.יהי יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3< n+1>3</math> קדקודים ו- <math>m\ge n+1\leq m </math> צלעות.
''אפשרות 1: 0'' - קיים <math>v\in V</math> קדקוד מדרגה 10 - כלומר אין לו שכנים. נוריד את אז נביט בגרף בלי הקדקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם <math>n</math> קדקודים ו<math>n\leq m-1 </math> צלעות. לפי הנחת , ומהנחת האינדוקציה קיים נקבל שיש בו מעגל. ; זהו מעגל זה קיים גם בגרף בו התחלנוהמקורי.
''אפשרות 21'': לכל קדקוד יש דרגה גדולה שווה 2. נבחר קיים <math>v_0v\in V</math> ונצא ממנו לאחד משכניומדרגה 1. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ נוריד את הקדקוד הזה (ואת הצלע שחלה בו) ונקבל גרף חדש עם <math>v\to un</math> הצעד הבא לא יהיה קדקודים ו<math>um-1 \to vge n </math> (זה אפשרי כי כל קדקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב)צלעות. כיוון שיש מספר סופי של קדקודים נקבל חזרה על קדקוד בשלב כלשהולפי הנחת האינדוקציה קיים בו מעגל. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!זה קיים גם בגרף בו התחלנו.
''אפשרות 2'': לכל קדקוד דרגה גדולה שווה 2. נבחר <math>v_0\in V</math> ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ <math>v\to u</math> הצעד הבא לא יהיה <math>u\to v</math> (זה אפשרי כי כל קדקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קדקודים נקבל חזרה על קדקוד כלשהו בשלב כלשהו. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!
'''פתרון:תרגיל''' נבנה פונקציה : יהי <math>f:V\to \{0,1,\dots n-1\} G</math> המוגדרת גרף מסדר <math>v\mapsto deg(v)n>1</math>. הוכח שקיימים 2 קדקודים בעלי אותה דרגה.
'''פתרון:''' נביט בפונקציית הדרגה <math>\operatorname{deg}:V \to \{0,1,\dots,n-1\}</math> השולחת כל איבר אל הדרגה שלו: <math>v\mapsto deg(v)</math>; כדי להבין את התמונה של הפונקציה, נשים לב שיש שני מקרים:#אם קיים קדקוד מדרגה <math>n-1 אזי </math>, אז הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה נוכל להגדיר מתקיים <math>\operatorname{Im}(f:V) \to subseteq \{1,\dots n-1\} </math>.#אם אין קדקוד מדרגה <math>n-1</math> אז<math>\operatorname{Im}(f) \subseteq \{0,1,\dots n-2\} </math>.
