=תרגילים=
==תרגיל:==
יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קודקודים.
אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל.
אפשרות 2: לכל קודקוד יש דרגה גדולה שווה 2. נבחר <math>v_0\in V</math> ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ <math>v\to u</math> הצעד הבא לא יהיה <math>u\to v</math> (זה אפשרי כי כל קודקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קודקודים נקבל חזרה על קודקוד בשלב כלשהוא. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!
== תרגיל ==
יהי G גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר <math>1<n</math>. הוכח שקיימים 2 קודקודים בעל אותה דרגה.
הוכחה:
נבנה פונקציה <math>f:V\to \{0,1,\dots n-1\} </math> המוגדרת <math>v\mapsto deg(v)</math>.
אם קיים קודקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קודקוד מדרגה אפס. במקרה זה נוכל להגדיר
<math>f:V\to \{1,\dots n-1\} </math>.
אם אין קודקוד כזה אז נוכל להגדיר <math>f:V\to \{0,1,\dots n-2\} </math>.
בשני המקרים קיבלנו כי <math>#dom(f)=#V=n, #Im(f)=n-1</math> ולכן <math>f</math> אינה חח"ע.
כלומר קיימים <math>v_1\neq v_2</math> כך ש <math>f(v_1)=f(v_2)</math> כלומר בעלי דרגה שווה
==תרגיל:==