שינויים

עבור גרף לא מכוון <math>G=(V,E)</math> נגדיר יחס שקילות <math>\to </math> על <math>V</math>, כך: לכל <math> v,u\in V</math> מתקיים <math> v\to u</math> אמ"מ קיים מסלול מ<math>v</math> ל-<math>u</math> (כלומר <math>u \to v \iff d(v,u,v)<\infty </math>).

# ''רפלקסיבי'' - לכל קדקוד<math>v</math>, המסלול <math>(v)</math> עושה את העבודה.# ''סימטרי'' - אם <math> vu\to uv</math>, אז יש מסלול <math> (v_0,\dots,v_n)</math> בין <math>vu</math> ל-<math>uv</math>. נביט במסלול ההפוך - <math> (v_n, v_{n-1}\dots ,v_1,v_0)</math> - זהו מסלול בין <math>uv</math> ל-<math>vu</math>, ולכן <math>u v \to vu</math>.# ''טרנזיטיבי'' - אם <math> vu\to uv</math> וגם <math> uv\to tw</math>, אז יש מסלולים <math> (v_1,\dots,v_n)</math> ו-<math> (v_1',\dots,v_n')</math>. היות ש-<math> v_n=v=v_1'</math>, נביט במסלול <math> (v_1,\dots,v_n=v_1',\dots,v_n')</math> - זהו מסלול המעיד על כך ש-<math> vu\to tw</math>.

'''==תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קדקודים.=אם נניח כ בגרף מתקיים <math>n\leq m forall v\in V : \operatorname{degre}(v)\geq 2</math> צלעות אזי אז בגרף יש מעגל.

'''פתרון''': באינדוקציהנבחר <math>v_0\in V</math> ונצא ממנו לאחד משכניו.מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ <math>v\to u</math> הצעד הבא לא יהיה <math>u\to v</math> (זה אפשרי כי כל קדקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קדקודים נקבל חזרה על קדקוד כלשהו בשלב כלשהו. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!

עבור ==תרגיל==יהי <math>nG=3(V,E)</math> אזי יש מדובר במשולש גרף, ונסמן <math>\delta_G=\underset{v\in V}{\min}\{deg(לא יכול להיות יותר מ -4 צלעות ב-3 קדקודיםV) ואכן מתקיים כי יש מעגל\}</math> את הדרגה המינימלית בגרף. נניח <math>\delta_G\geq 1</math>.הוכיחו:

נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>א.יהי יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3< n+1</math> קדקודים ו- יש בגרף מסלול פשוט מאורך לפחות <math>n+1\leq m delta_G</math> צלעות.

אפשרות 1: קיים <math>v\in V</math> מדרגה 1ב. נוריד את הקדקוד הזה (ואת כל הצלעות שחלות בו) ונקבל גרף חדש עם יש בגרף מעגל פשוט מאורך לפחות <math>n</math> קדקודים ו<math>n\leq m-delta_G+1 </math> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.

'''תרגיל''': ב. יהי <math>G(v_1,v_2,\dots ,v_k)</math> גרף מסלול פשוט (ללא לולאות וללא צלעות מקבילות) מסדר מאורך מקסימלי. ראינו שכל שכני הראשון במסלול, ולכן מספיק לקחת את המסלול עד שמגיעים לאחרון השכנים, ואז לחזור חזרה ל <math>1<nv_1</math>. הוכח שקיימים 2 קדקודים בעל אותה דרגהולקבל מעגל פשוט מהאורך המתאים.

'''פתרון:''' נבנה פונקציה ==תרגיל==יהי <math>f:G=(V\to \{0,1,\dots E)</math> גרף בעל <math>n-1\} ge 3</math> המוגדרת קדקודים. ו-<math>vm \mapsto deg(v)ge n </math>צלעות. אזי בגרף יש מעגל.

אם קיים קדקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה נוכל להגדיר <math>f'''פתרון''':V\to \{1,\dots n-1\} </math>באינדוקציה.

אם אין קדקוד כזה אז נוכל להגדיר עבור <math>f:V\to \{0,1,\dots n-2\} =3</math>הגרף הוא בהכרח משולש (לא יכולות להיות יותר מ-3 צלעות עבור 3 קדקודים) ואכן יש מעגל.

בשני המקרים קיבלנו נניח כי הטענה נכונה עבור <math>|dom(f)|=|V|=n, |Im(f)|=</math> ונוכיח עבור <math>n-+1</math> ולכן . יהי <math>fG</math> אינה חח"ע. כלומר קיימים בעל <math>v_1\neq v_2n+1>3</math> כך ש קדקודים ו- <math>f(v_1)=f(v_2)m\ge n+1</math> כלומר בעלי דרגה שווהצלעות.

'''תרגיל'אפשרות 1'': יהיה קיים <math>G=(v\in V,E)</math> מדרגה 1. נוריד את הקדקוד הזה (ואת הצלע שחלה בו) ונקבל גרף פשוט חדש עם 100 <math>n</math> קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי ו<math>Gm-1 \ge n </math> קשירצלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.

'''פתרון'אפשרות 2'': יהיו <math>v,u\in V</math> צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).נניח כי הם שונים אזי ב<math>|[v]|,|[u]|\geq 50</math> והם זרים. לכן <math>[v]=[u]=50</math> אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל לכל קדקוד קטנה דרגה גדולה שווה ל 492. סתירהולפי תרגיל קודם יש מעגל

'''תרגילפתרון:''': יהי גרף לא מכוון נביט בפונקציית הדרגה <math>G=(\operatorname{deg}:V\to \{0,E1,\dots,n-1\}</math> השולחת כל איבר אל הדרגה שלו: <math>v\mapsto \operatorname{deg}(v)</math>. הוכח כי ; כדי להבין את התמונה של הפונקציה, נשים לב שיש שני מקרים:#אם קיים קדקוד מדרגה <math>n-1</math>, אז הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה מתקיים <math>\forall voperatorname{Im}(f) \in V : subseteq \{1,\dots n-1\} </math>.#אם אין קדקוד מדרגה <math>n-1</math> אז <math>\textoperatorname{degreeIm}(vf)\geq subseteq \{0,1,\dots n-2\} </math> אז בגרף יש מעגל.

'''פתרון''': בגרף יש יותר מ 2 קדקודים (אחרת לא יהיה להם 2 שכנים).לפי משפט לחיצת הידיים מתקיים בשני המקרים קיבלנו כי <math>2|E|= \sum_operatorname{v\in Vdom}(f)|=|V|=n, |\textoperatorname{degreeIm}(vf)|\geq \sum_{vle n-1</math> ולכן <math>f</math> אינה חח"ע. כלומר קיימים <math>v_1\in V}2 neq v_2</math> כך ש <math>f(v_1)=2|V|f(v_2)</math>ולכן מספר הצלעות גדול כלומר בעלי דרגה שווה ממספר הקדקודים. לפי משפט קודם קיים מעגל בגרף.

'''==תרגיל''': יהי גרף לא מכוון ==יהיה <math>G=(V,E)</math> ללא מעגלים גרף פשוט עם <math>|V|\geq 2</math>100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי קיימים <math>v_1,v_2\in VG</math> כך שדרגתם לכל היותר 1קשיר.

'''פתרון''': לפי תרגיל קודם קיים יהיו <math>v,u\in V</math> . צריך להוכיח כי <math>[v]=[u]</math> (כך שדרגתו לכל היותר 1 נסמן את רכיב הקשירות).נניח כי הם שונים, אזי ב<math>|[v]|,|[u]|\geq 51</math> (אחרת לכל הקדקודים יש דרגה הקודוקד + לפחות 2 ואז יש מעגל לפי תרגיל קודם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}</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|\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>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.  בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר! ==תרגיל==הוכח/הפרך:# אם מתקיים <math>\forall v \in V: \operatorname{deg}(v)\ge2</math>, אז <math>G</math> קשיר.# קיים גרף בן שישה קדקודים 1,2,3,4,4,5.# קיים גרף בן שישה קדקודים 1,2,3,4,5,5. '''פתרון''':# לא נכון, למשל שני משולשים מופרדים.# לא נכון, כי סכום הדרגות אי-זוגי, בסתירה למשפט לחיצת הידיים.# הפעם משפט לחיצת הידיים לא נכשל, אך זה עדיין לא נכון - אילו היו שני קדקודים מדרגה 5, הר שכל הקדקודים היו מחוברים אל שניהם, ולכן אין קדקוד מדרגה 1. ==תרגיל==יהא <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. ==תרגיל==יהא <math>G=(V,E)</math> גרף פשוט סופי לא מכוון קשיר בעל מעגל יחיד עם <math>3\leq |V|</math>. הוכיחו כי <math>|E|=|V|</math>  פתרון: נסמן את המעגל היחידי ב G ב <math>C=(v_0,\dots,v_n)</math>. טענה: <math>|V|\leq |E|</math> הוכחה: נסתכל על הגרף <math>G'=(V,E\setminus \{v_{n-1},v_n\})</math> הוא בעל <math>|E|-1</math> קשתות אך עדיין קשיר (כי אם יש מסלול המערב את הקשת שהורדה ניתן להחליף אותה <math>C=(v_0,\dots,v_{n-1})</math>.) לכן לפי הרצאה יש לו לפחות <math>|V|-1</math> קשתות ולכן <math>|V|-1\leq |E|-1</math> ואחרי העברת אגפים נקבל את המבוקש. טענה: <math>|E|\leq |V|</math> הוכחה: נניח בשלילה כי <math>|V|+1\leq |E|</math> נסתכל על הגרף <math>G'=(V,E\setminus \{v_{n-1},v_n\})</math>הוא בעל <math>|V| \leq|E|-1</math> קשתות אך הרסנו את המעגל היחידי שהיה ב G אבל לפי תרגיל ממקודם אם מספר הצלעות גדול שווה ממספר הקודקודים יש בו מעגל. סתירה.

אם <math>v</math> שכן ==תרגיל==א. מהו הקוטר המקסימלי של גרף קשיר עם <math>v_1n</math> אזי <math>v,v_2</math> בעלי דרגה לכל היותר 1. קודקודים?

אם <math>v</math> שכן ב. מהו המספר המינימלי של קשתות בגרף עם <math>v_2n</math> אזי <math>v,v_1</math> בעלי דרגה לכל היותר 1. קודקודים וקוטר 2?

אם א. <math>vn-1</math> . לא שכן של יכול להיות יותר כי הקוטר מוגדר כמרחק המקסימלי בין קודקודים, ומרחק הוא אורך המסלול הקצר, ומסלול קצר לא מכיל מעגלים, ולכן מכיל לכל היותר <math>v_1,v_2n</math> אזי קודקודים, ולכן לכל היותר <math>v,v_1,v_2n-1</math> בעלי דרגה לכל היותר קשתות. גרף קו הוא עם קוטר <math>n-1</math> כי זה המרחק בין הימני ביותר לשמאלי ביותר, לכן זה הקוטר המקסימלי.

בכל מקרה קיבלנו ב. <math>n-1</math>. לא יכול להיות פחות כי אז הגרף לא יהיה קשיר וקטרו יהיה אינסוף ולא 2. גרף כוכב (יש קודקוד <math>u</math> המקיים <math>E=\{\{u,v\}:u\neq v\}</math> כלומר, הוא מחובר לכולם ואין עוד קשתות) הוא עם <math>n-1</math> קשתות וקוטר 2, כי קיימים המרחק בין שני קודקודים שאינם <math>u</math> הוא 2 קדקודים בעלי דרגה (ואם אחד מהם הוא <math>u</math> אז 1 לכל היותר!).