88-195 בדידה לתיכוניסטים תשעא/מערך שיעור/שיעור 11: הבדלים בין גרסאות בדף

מתוך Math-Wiki
אין תקציר עריכה
 
(27 גרסאות ביניים של 5 משתמשים אינן מוצגות)
שורה 50: שורה 50:
'''הגדרה''': המרחק בין <math>v,u\in V</math> הוא המסלול עם אורך מינימלי בין <math>v,u\in V</math>. אם אין מסלול בין הנקודות, אומרים שהמרחק הוא אינסוף. מסמנים את המרחק <math>d(u,v)</math>, ואם יש צורך להדגיש את הגרפים אז מסמנים <math>d_G(u,v)</math>.
'''הגדרה''': המרחק בין <math>v,u\in V</math> הוא המסלול עם אורך מינימלי בין <math>v,u\in V</math>. אם אין מסלול בין הנקודות, אומרים שהמרחק הוא אינסוף. מסמנים את המרחק <math>d(u,v)</math>, ואם יש צורך להדגיש את הגרפים אז מסמנים <math>d_G(u,v)</math>.


ה'''קוטר''' של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר <math>\text{diam}(G)=\max_{u,v\in V}{d(v,u)}</math>
ה'''קוטר''' של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר <math>\operatorname{diam}(G)=\max_{u,v\in V}{d(v,u)}</math>


===בניה===
===בניה===
עבור גרף לא מכוון <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)<\infty </math>).
עבור גרף לא מכוון <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(u,v)<\infty </math>).


'''תרגיל''': הוכח כי זהו יחס שקילות.
'''תרגיל''': הוכח כי זהו יחס שקילות.


'''פתרון''':
'''פתרון''':
# ''רפלקסיבי'' - לכל קדקוד, המסלול <math>(v)</math> עושה את העבודה.
# ''רפלקסיבי'' - לכל קדקוד <math>v</math>, המסלול <math>(v)</math> עושה את העבודה.
# ''סימטרי'' - אם <math> v\to u</math>, אז יש מסלול <math> (v_0,\dots,v_n)</math> בין <math>v</math> ל-<math>u</math>. נביט במסלול ההפוך - <math> (v_n, v_{n-1}\dots ,v_1,v_0)</math> - זהו מסלול בין <math>u</math> ל-<math>v</math>, ולכן <math>u \to v</math>.
# ''סימטרי'' - אם <math> u\to v</math>, אז יש מסלול <math> (v_0,\dots,v_n)</math> בין <math>u</math> ל-<math>v</math>. נביט במסלול ההפוך - <math> (v_n, v_{n-1}\dots ,v_1,v_0)</math> - זהו מסלול בין <math>v</math> ל-<math>u</math>, ולכן <math>v \to u</math>.
# ''טרנזיטיבי'' - אם <math> v\to u</math> וגם <math> u\to t</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> v\to t</math>.
# ''טרנזיטיבי'' - אם <math> u\to v</math> וגם <math> v\to w</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> u\to w</math>.


'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.
'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.
הגדרה: G יקרא קשיר אם בין כל שני קודקודים יש מסלול. זה שקול לכך שיש רכיב קשירות או באופן שקול <math>\forall v\in V:[v]_{\to}=V</math>


'''דוגמא''': ציור חביב לפי דעת המתרגל.
'''דוגמא''': ציור חביב לפי דעת המתרגל.


=תרגילים נוספים=
=תרגילים נוספים=
'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math> בעל <math>3\leq n</math> קדקודים.
==תרגיל==
אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל.
נניח כ בגרף מתקיים <math>\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>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>G=(V,E)</math> גרף בעל <math>n\ge 3</math> קדקודים. ו-<math>m \ge n </math> צלעות. אזי בגרף יש מעגל.


'''פתרון''': באינדוקציה.
'''פתרון''': באינדוקציה.


עבור <math>n=3</math> אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קדקודים) ואכן מתקיים כי יש מעגל.
עבור <math>n=3</math> הגרף הוא בהכרח משולש (לא יכולות להיות יותר מ-3 צלעות עבור 3 קדקודים) ואכן יש מעגל.


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


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


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


''אפשרות 2'': לכל קדקוד דרגה גדולה שווה 2. ולפי תרגיל קודם יש מעגל


'''תרגיל''': יהי <math>G</math> גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר <math>1<n</math>. הוכח שקיימים 2 קדקודים בעל אותה דרגה.
==תרגיל==
יהי <math>G</math> גרף מסדר <math>n>1</math>. הוכח שקיימים 2 קדקודים בעלי אותה דרגה.


'''פתרון:''' נבנה פונקציה <math>f:V\to \{0,1,\dots n-1\} </math> המוגדרת <math>v\mapsto deg(v)</math>.  
'''פתרון:''' נביט בפונקציית הדרגה <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>.


אם קיים קדקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה נוכל להגדיר
בשני המקרים קיבלנו כי <math>|\operatorname{dom}(f)|=|V|=n, |\operatorname{Im}(f)|\le n-1</math> ולכן <math>f</math> אינה חח"ע.
<math>f:V\to \{1,\dots n-1\} </math>.
כלומר קיימים <math>v_1\neq v_2</math> כך ש <math>f(v_1)=f(v_2)</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> כלומר בעלי דרגה שווה
יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי <math>G</math> קשיר.


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


'''תרגיל''': יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי <math>G</math> קשיר.
'''הערה:''' אפשר להכליל את התרגיל, ולהפוך אותו לתרגיל על קוטר של גרף: יהי <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>[v]=[u]</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>|[v]|,|[u]|\geq 50</math> והם זרים. לכן <math>[v]=[u]=50</math> אבל ברכיב קשירות שיש בו 50 קדקודים דרגת כל קדקוד קטנה שווה ל 49. סתירה


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


'''תרגיל''': יהי גרף לא מכוון <math>G=(V,E)</math>. הוכח כי אם <math>\forall v\in V : \text{degree}(v)\geq 2</math> אז בגרף יש מעגל.
'''פתרון''': לפי תרגיל קודם קיים <math>v\in V</math> כך שדרגתו לכל היותר 1 (אחרת לכל הקדקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם).


'''פתרון''': בגרף יש יותר מ 2 קדקודים (אחרת לא יהיה להם 2 שכנים).
נמשיך באינדוקציה על <math>n</math>, מספר הקדקודים בגרף.
לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\text{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>
ולכן מספר הצלעות גדול שווה ממספר הקדקודים. לפי משפט קודם קיים מעגל בגרף.


אם <math>n=2</math> אזי או שהגרף הוא 2 נקודות ללא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 2 הנקודות של הגרף הן מדרגה קטנה שווה ל-1.


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


'''פתרון''': לפי תרגיל קודם קיים <math>v\in V</math> כך שדרגתו לכל היותר 1 (אחרת לכל הקדקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם. סתירה!).
נבחר את הקדקוד <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.  


נמשיך באינדוקציה על <math>n</math> מספר הקדקודים בגרף.
בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר!


אם <math>n=2</math> אזי או שהגרף הוא 2 נקודות לא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 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.


כעת נניח כי הטענה נכונה עבור <math>n\geq 2</math>. נוכיח  את הטענה עבור <math>n+1</math>.
'''פתרון''':
# לא נכון, למשל שני משולשים מופרדים.
# לא נכון, כי סכום הדרגות אי-זוגי, בסתירה למשפט לחיצת הידיים.
# הפעם משפט לחיצת הידיים לא נכשל, אך זה עדיין לא נכון - אילו היו שני קדקודים מדרגה 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>v\in V</math> שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו אזי נקבל גרף עם <math>n</math> קדקודים. לפי הנחת האינדוקציה יש בו 2 קדקודים<math>v_1,v_2</math> בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את <math>v</math> שהשמטנו).  
נסתכל על הגרף <math>G'=(V,E\setminus \{v_{n-1},v_n\})</math>
הוא בעל <math>|V| \leq|E|-1</math> קשתות אך הרסנו את המעגל היחידי שהיה ב G אבל לפי תרגיל ממקודם אם מספר הצלעות גדול שווה ממספר הקודקודים יש בו מעגל. סתירה.


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


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


אם <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.  
א. <math>n-1</math>. לא יכול להיות יותר כי הקוטר מוגדר כמרחק המקסימלי בין קודקודים, ומרחק הוא אורך המסלול הקצר, ומסלול קצר לא מכיל מעגלים, ולכן מכיל לכל היותר <math>n</math> קודקודים, ולכן לכל היותר <math>n-1</math> קשתות. גרף קו הוא עם קוטר <math>n-1</math> כי זה המרחק בין הימני ביותר לשמאלי ביותר, לכן זה הקוטר המקסימלי.


בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר!.
ב. <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).

גרסה אחרונה מ־07:11, 19 באוגוסט 2019

חזרה למערכי התרגול

הגדרות בסיסיות

הגדרה: גרף [math]\displaystyle{ G }[/math] מעל קבוצה [math]\displaystyle{ V }[/math] הוא זוג סדור [math]\displaystyle{ G=(V,E) }[/math] כאשר [math]\displaystyle{ E \subseteq V\times V }[/math] - כלומר קבוצה המכילה זוגות סדורים מאיברי [math]\displaystyle{ V }[/math].

הקבוצה [math]\displaystyle{ V }[/math] היא קבוצת הקדקודים של הגרף, והקבוצה [math]\displaystyle{ E }[/math] היא קבוצת הקשתות/צלעות של הגרף.

הגדרה: הסדר של גרף [math]\displaystyle{ G=(V,E) }[/math] הוא [math]\displaystyle{ |V| }[/math]. גרף יקרא סופי אם הסדר שלו סופי, וקבוצת הקשתות [math]\displaystyle{ E }[/math] סופית.

הגדרה: גרף [math]\displaystyle{ G }[/math] ייקרא לא מכוון אם היחס [math]\displaystyle{ E }[/math] הוא סימטרי, כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון, אין משמעות לכיוון הצלע, ולכן לעתים מסמנים [math]\displaystyle{ (u,v) }[/math] בתור [math]\displaystyle{ \{u,v\} }[/math].

דוגמא: [math]\displaystyle{ V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\} }[/math] מייצג משולש. הסדר שלו הוא 3, כמספר הקדקודים במשולש. זהו גרף סופי.

דוגמא: נביט בקבוצה [math]\displaystyle{ \mathbb{Z}\times\mathbb{Z} }[/math], ובגרף [math]\displaystyle{ G }[/math] מעליה, בו מחברים בין כל שני קדקודים במרחק 1 זה מזה - מתקבלת רשת אינסופית. זהו גרף אינסופי, בו לכל קדקוד יש ארבעה שכנים.

הערה: שימו לב שמהניסוח לעיל נובע-

  1. בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- [math]\displaystyle{ \exists (v,v) \in E }[/math].
  2. צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (כי [math]\displaystyle{ E }[/math] קבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.

הבהרה: אנחנו נעסוק בגרפים סופיים, לא מכוונים, בלי צלעות כפולות ובלי לולאות.

הגדרה יהיה [math]\displaystyle{ G=(V,E) }[/math]. נאמר כי [math]\displaystyle{ v,w\in V }[/math] שכנים אם [math]\displaystyle{ (v,w)\in E }[/math]. במקרה זה נאמר כי הצלע [math]\displaystyle{ \{v,w\}\in E }[/math] חלה ב [math]\displaystyle{ w }[/math] (או חלה ב [math]\displaystyle{ v }[/math])

את קבוצת השכנים של [math]\displaystyle{ u }[/math] מסמנים [math]\displaystyle{ \Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\} }[/math].

הדרגה של [math]\displaystyle{ u }[/math], המסומנת [math]\displaystyle{ \text{degree}(u) }[/math], היא מספר הצלעות החלות ב [math]\displaystyle{ u }[/math], כלומר [math]\displaystyle{ |\Gamma(u)| }[/math].


דוגמא: במשולש, כל 2 קדקודים שכנים. כל קדקוד מדרגה 2: השכנים של כל קדקוד הם שני הקדקודים האחרים.


משפט (לחיצת הידיים)

יהי [math]\displaystyle{ G=(V,E) }[/math] גרף לא מכוון. אזי [math]\displaystyle{ \sum_{v\in V}\text{degree}(v)=2|E| }[/math].

תרגיל

נאמר כי גרף [math]\displaystyle{ G=(V,E) }[/math] הוא [math]\displaystyle{ k }[/math]-רגולרי אם הדרגה של כל קדקוד שווה ל-[math]\displaystyle{ k }[/math]. למשל, משולש הוא גרף 2-רגולרי.

הוכח כי אם [math]\displaystyle{ k,n }[/math] אי-זוגיים, לא קיים גרף [math]\displaystyle{ k }[/math]-רגולרי מסדר [math]\displaystyle{ n }[/math].

הוכחה:

לפי משפט לחיצת הידיים [math]\displaystyle{ 2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k }[/math]. לכן [math]\displaystyle{ nk }[/math] זוגי, ולכן [math]\displaystyle{ k }[/math] זוגי או [math]\displaystyle{ n }[/math] זוגי.

הגדרות נוספות

יהי [math]\displaystyle{ G=(V,E) }[/math] גרף לא מכוון. סדרת קדקודים (סדורה) [math]\displaystyle{ (v_0,v_1,\dots,v_n) }[/math] נקראת מסלול אם [math]\displaystyle{ \forall i : \{v_i,v_{i+1}\}\in E }[/math] וגם כל הצלעות שונות - כלומר לכל [math]\displaystyle{ i\neq j }[/math] מתקיים [math]\displaystyle{ (v_i,v_{i+1}) \neq (v_j,v_{j+1}) }[/math].

מסלול יקרא פשוט אם כל הקדקודים [math]\displaystyle{ (v_0,v_1,\dots,v_n) }[/math] שונים זה מזה, פרט אולי ל [math]\displaystyle{ v_0=v_n }[/math], ובמקרה זה המסלול נקרא מעגל. אורך המסלול [math]\displaystyle{ (v_0,v_1,\dots,v_n) }[/math] הוא [math]\displaystyle{ n }[/math], והנקודות [math]\displaystyle{ v_0 }[/math] ו-[math]\displaystyle{ v_n }[/math] נקראות נקודות ההתחלה והסיום של המסלול.

הגדרה: המרחק בין [math]\displaystyle{ v,u\in V }[/math] הוא המסלול עם אורך מינימלי בין [math]\displaystyle{ v,u\in V }[/math]. אם אין מסלול בין הנקודות, אומרים שהמרחק הוא אינסוף. מסמנים את המרחק [math]\displaystyle{ d(u,v) }[/math], ואם יש צורך להדגיש את הגרפים אז מסמנים [math]\displaystyle{ d_G(u,v) }[/math].

הקוטר של גרף [math]\displaystyle{ G=(V,E) }[/math] מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר [math]\displaystyle{ \operatorname{diam}(G)=\max_{u,v\in V}{d(v,u)} }[/math]

בניה

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

תרגיל: הוכח כי זהו יחס שקילות.

פתרון:

  1. רפלקסיבי - לכל קדקוד [math]\displaystyle{ v }[/math], המסלול [math]\displaystyle{ (v) }[/math] עושה את העבודה.
  2. סימטרי - אם [math]\displaystyle{ u\to v }[/math], אז יש מסלול [math]\displaystyle{ (v_0,\dots,v_n) }[/math] בין [math]\displaystyle{ u }[/math] ל-[math]\displaystyle{ v }[/math]. נביט במסלול ההפוך - [math]\displaystyle{ (v_n, v_{n-1}\dots ,v_1,v_0) }[/math] - זהו מסלול בין [math]\displaystyle{ v }[/math] ל-[math]\displaystyle{ u }[/math], ולכן [math]\displaystyle{ v \to u }[/math].
  3. טרנזיטיבי - אם [math]\displaystyle{ u\to v }[/math] וגם [math]\displaystyle{ v\to w }[/math], אז יש מסלולים [math]\displaystyle{ (v_1,\dots,v_n) }[/math] ו-[math]\displaystyle{ (v_1',\dots,v_n') }[/math]. היות ש-[math]\displaystyle{ v_n=v=v_1' }[/math], נביט במסלול [math]\displaystyle{ (v_1,\dots,v_n=v_1',\dots,v_n') }[/math] - זהו מסלול המעיד על כך ש-[math]\displaystyle{ u\to w }[/math].

הגדרה מחלקות השקילות של יחס זה נקראים רכיבי קשירות.

הגדרה: G יקרא קשיר אם בין כל שני קודקודים יש מסלול. זה שקול לכך שיש רכיב קשירות או באופן שקול [math]\displaystyle{ \forall v\in V:[v]_{\to}=V }[/math]

דוגמא: ציור חביב לפי דעת המתרגל.

תרגילים נוספים

תרגיל

נניח כ בגרף מתקיים [math]\displaystyle{ \forall v\in V : \operatorname{degre}(v)\geq 2 }[/math] אז בגרף יש מעגל.

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

תרגיל

יהי [math]\displaystyle{ G=(V,E) }[/math] גרף, ונסמן [math]\displaystyle{ \delta_G=\underset{v\in V}{\min}\{deg(V)\} }[/math] את הדרגה המינימלית בגרף. נניח [math]\displaystyle{ \delta_G\geq 1 }[/math]. הוכיחו:

א. יש בגרף מסלול פשוט מאורך לפחות [math]\displaystyle{ \delta_G }[/math].

ב. יש בגרף מעגל פשוט מאורך לפחות [math]\displaystyle{ \delta_G+1 }[/math].

פתרון

א. יהי [math]\displaystyle{ (v_1,v_2,\dots ,v_k) }[/math] מסלול פשוט מאורך מקסימלי. מתקיים: [math]\displaystyle{ \deg(v_1)\geq \delta_G }[/math]. טענה: כל שכניו נמצאים במסלול. הוכחה: אחרת אפשר להוסיף שכן שלא במסלול לתחילת המסלול ולקבל מסלול פשוט ארוך יותר בסתירה למקסימליות. לכן אורך המסלול לפחות כמו [math]\displaystyle{ \delta_G }[/math].

ב. יהי [math]\displaystyle{ (v_1,v_2,\dots ,v_k) }[/math] מסלול פשוט מאורך מקסימלי. ראינו שכל שכני הראשון במסלול, ולכן מספיק לקחת את המסלול עד שמגיעים לאחרון השכנים, ואז לחזור חזרה ל [math]\displaystyle{ v_1 }[/math] ולקבל מעגל פשוט מהאורך המתאים.

תרגיל

יהי [math]\displaystyle{ G=(V,E) }[/math] גרף בעל [math]\displaystyle{ n\ge 3 }[/math] קדקודים. ו-[math]\displaystyle{ m \ge n }[/math] צלעות. אזי בגרף יש מעגל.

פתרון: באינדוקציה.

עבור [math]\displaystyle{ n=3 }[/math] הגרף הוא בהכרח משולש (לא יכולות להיות יותר מ-3 צלעות עבור 3 קדקודים) ואכן יש מעגל.

נניח כי הטענה נכונה עבור [math]\displaystyle{ n }[/math] ונוכיח עבור [math]\displaystyle{ n+1 }[/math]. יהי [math]\displaystyle{ G }[/math] בעל [math]\displaystyle{ n+1\gt 3 }[/math] קדקודים ו- [math]\displaystyle{ m\ge n+1 }[/math] צלעות.

אפשרות 0 - קיים קדקוד מדרגה 0 - כלומר אין לו שכנים. אז נביט בגרף בלי הקדקוד הזה, ומהנחת האינדוקציה נקבל שיש בו מעגל; זהו מעגל גם בגרף המקורי.

אפשרות 1: קיים [math]\displaystyle{ v\in V }[/math] מדרגה 1. נוריד את הקדקוד הזה (ואת הצלע שחלה בו) ונקבל גרף חדש עם [math]\displaystyle{ n }[/math] קדקודים ו[math]\displaystyle{ m-1 \ge n }[/math] צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.

אפשרות 2: לכל קדקוד דרגה גדולה שווה 2. ולפי תרגיל קודם יש מעגל

תרגיל

יהי [math]\displaystyle{ G }[/math] גרף מסדר [math]\displaystyle{ n\gt 1 }[/math]. הוכח שקיימים 2 קדקודים בעלי אותה דרגה.

פתרון: נביט בפונקציית הדרגה [math]\displaystyle{ \operatorname{deg}:V \to \{0,1,\dots,n-1\} }[/math] השולחת כל איבר אל הדרגה שלו: [math]\displaystyle{ v\mapsto \operatorname{deg}(v) }[/math]; כדי להבין את התמונה של הפונקציה, נשים לב שיש שני מקרים:

  1. אם קיים קדקוד מדרגה [math]\displaystyle{ n-1 }[/math], אז הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה מתקיים

[math]\displaystyle{ \operatorname{Im}(f) \subseteq \{1,\dots n-1\} }[/math].

  1. אם אין קדקוד מדרגה [math]\displaystyle{ n-1 }[/math] אז [math]\displaystyle{ \operatorname{Im}(f) \subseteq \{0,1,\dots n-2\} }[/math].

בשני המקרים קיבלנו כי [math]\displaystyle{ |\operatorname{dom}(f)|=|V|=n, |\operatorname{Im}(f)|\le n-1 }[/math] ולכן [math]\displaystyle{ f }[/math] אינה חח"ע. כלומר קיימים [math]\displaystyle{ v_1\neq v_2 }[/math] כך ש [math]\displaystyle{ f(v_1)=f(v_2) }[/math] כלומר בעלי דרגה שווה.


תרגיל

יהיה [math]\displaystyle{ G=(V,E) }[/math] גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי [math]\displaystyle{ G }[/math] קשיר.

פתרון: יהיו [math]\displaystyle{ v,u\in V }[/math]. צריך להוכיח כי [math]\displaystyle{ [v]=[u] }[/math] (כך נסמן את רכיב הקשירות). נניח כי הם שונים, אזי ב[math]\displaystyle{ |[v]|,|[u]|\geq 51 }[/math] ( הקודוקד + לפחות 50 שכנים). אלו הם שני מרכיבי קשירות שונים ולכן הם זרים, ומכך שבגרף יש לכל הפחות 102 קדקודים, סתירה.

הערה: אפשר להכליל את התרגיל, ולהפוך אותו לתרגיל על קוטר של גרף: יהי [math]\displaystyle{ G=(V,E) }[/math] גרף עם [math]\displaystyle{ |V|=n }[/math]. הוכיחו שאם דרגת כל קודקוד היא לפחות [math]\displaystyle{ \frac{n-1}{2} }[/math] אז [math]\displaystyle{ diam(G)\leq 2 }[/math], ובפרט [math]\displaystyle{ G }[/math] קשיר.

הוכחה: יהיו [math]\displaystyle{ v,u\in V }[/math]. אם הם שכנים אז [math]\displaystyle{ d(v,u)=1 }[/math]. אם לא, אז נניח בשלילה שאין להם שכן משותף ונקבל ש- [math]\displaystyle{ \Gamma(v)\cap \Gamma(u)=\varnothing }[/math], ובנוסף [math]\displaystyle{ |\Gamma(v)|,|\Gamma(u)|\geq \frac{n-1}{2} }[/math], ולכן יש בגרף לפחות [math]\displaystyle{ |\Gamma(v)\cup \Gamma(u)\cup \{v,u\}|=2\cdot \frac{n-1}{2}+2=n+1 }[/math] קודקודים (נובע מכך שהאיחוד זר) בסתירה. לכן יש להם שכן משותף ולכן [math]\displaystyle{ d(v,u)=2 }[/math]. בסה"כ נקבל [math]\displaystyle{ \forall v,u:d(v,u)\leq 2 }[/math] ולכן [math]\displaystyle{ diam(G)\leq 2 }[/math].

תרגיל

יהי [math]\displaystyle{ G=(V,E) }[/math] גרף ללא מעגלים עם [math]\displaystyle{ |V|\geq 2 }[/math]. הוכח כי קיימים [math]\displaystyle{ v_1,v_2\in V }[/math] כך שדרגתם לכל היותר 1.

פתרון: לפי תרגיל קודם קיים [math]\displaystyle{ v\in V }[/math] כך שדרגתו לכל היותר 1 (אחרת לכל הקדקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם).

נמשיך באינדוקציה על [math]\displaystyle{ n }[/math], מספר הקדקודים בגרף.

אם [math]\displaystyle{ n=2 }[/math] אזי או שהגרף הוא 2 נקודות ללא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 2 הנקודות של הגרף הן מדרגה קטנה שווה ל-1.

כעת נניח כי הטענה נכונה עבור [math]\displaystyle{ n\geq 2 }[/math]. נוכיח את הטענה עבור [math]\displaystyle{ n+1 }[/math].

נבחר את הקדקוד [math]\displaystyle{ v\in V }[/math] שדרגתו לכל היותר 1. נוריד אותו ואת הצלע שחלה בו (אם קיימת), ונקבל גרף עם [math]\displaystyle{ n }[/math] קדקודים. לפי הנחת האינדוקציה יש בו 2 קדקודים[math]\displaystyle{ v_1,v_2 }[/math] בעלי דרגה 1 לכל היותר. כעת נשוב לגרף המקורי (הכולל את [math]\displaystyle{ v }[/math] שהשמטנו). יש מספר מקרים:

  1. אם [math]\displaystyle{ v }[/math] שכן של [math]\displaystyle{ v_1 }[/math] אזי [math]\displaystyle{ v,v_2 }[/math] בעלי דרגה לכל היותר 1.
  2. אם [math]\displaystyle{ v }[/math] שכן של [math]\displaystyle{ v_2 }[/math] אזי [math]\displaystyle{ v,v_1 }[/math] בעלי דרגה לכל היותר 1.
  3. אם [math]\displaystyle{ v }[/math] שכן של [math]\displaystyle{ v_1,v_2 }[/math] - סתירה כי הדרגה של [math]\displaystyle{ v }[/math] היא 1 לכל היותר.
  4. אם [math]\displaystyle{ v }[/math] לא שכן של [math]\displaystyle{ v_1,v_2 }[/math] אזי [math]\displaystyle{ v,v_1,v_2 }[/math] בעלי דרגה לכל היותר 1.

בכל מקרה קיבלנו כי קיימים 2 קדקודים בעלי דרגה 1 לכל היותר!

תרגיל

הוכח/הפרך:

  1. אם מתקיים [math]\displaystyle{ \forall v \in V: \operatorname{deg}(v)\ge2 }[/math], אז [math]\displaystyle{ G }[/math] קשיר.
  2. קיים גרף בן שישה קדקודים 1,2,3,4,4,5.
  3. קיים גרף בן שישה קדקודים 1,2,3,4,5,5.

פתרון:

  1. לא נכון, למשל שני משולשים מופרדים.
  2. לא נכון, כי סכום הדרגות אי-זוגי, בסתירה למשפט לחיצת הידיים.
  3. הפעם משפט לחיצת הידיים לא נכשל, אך זה עדיין לא נכון - אילו היו שני קדקודים מדרגה 5, הר שכל הקדקודים היו מחוברים אל שניהם, ולכן אין קדקוד מדרגה 1.

תרגיל

יהא [math]\displaystyle{ G=(V,E) }[/math] גרף פשוט סופי לא מכוון. נניח כי [math]\displaystyle{ V=V_1\cup V_2 }[/math] איחוד זר (כלומר החיתוך [math]\displaystyle{ V_1\cap V_2=\emptyset }[/math]. עוד נניח כי קיים [math]\displaystyle{ v_i\in V_i }[/math] כך שקיימת קשת [math]\displaystyle{ (v_1,v_2)\in E }[/math] והיא הקשת היחידה בין [math]\displaystyle{ V_1 }[/math] ל [math]\displaystyle{ V_2 }[/math].

הוכיחו שקיים קודקוד בעל דרגה אי זוגית.

פתרון: נסתכל על תת הגרף [math]\displaystyle{ V_1 }[/math] אם [math]\displaystyle{ v_1 }[/math] בעל דרגה זוגית בו אז הוא יהיה בעל דרגה אי זוגית ב V. אחרת דרגתו ב V1 אי זוגית ולכן לפי משפט לחיצת הידיים שסכום הדרגות זוגיות, קיים עוד קודוד בעל דרגה אי זוגית ב V1. כיוון שהקשת היחידה בין [math]\displaystyle{ V_1 }[/math] ל [math]\displaystyle{ V_2 }[/math] היא [math]\displaystyle{ (v_1,v_2)\in E }[/math] נקבל כי קודקוד זה בעל דרגה אי זוגית גם ב G.

תרגיל

יהא [math]\displaystyle{ G=(V,E) }[/math] גרף פשוט סופי לא מכוון קשיר בעל מעגל יחיד עם [math]\displaystyle{ 3\leq |V| }[/math]. הוכיחו כי [math]\displaystyle{ |E|=|V| }[/math]

פתרון: נסמן את המעגל היחידי ב G ב [math]\displaystyle{ C=(v_0,\dots,v_n) }[/math].

טענה: [math]\displaystyle{ |V|\leq |E| }[/math]

הוכחה: נסתכל על הגרף [math]\displaystyle{ G'=(V,E\setminus \{v_{n-1},v_n\}) }[/math] הוא בעל [math]\displaystyle{ |E|-1 }[/math] קשתות אך עדיין קשיר (כי אם יש מסלול המערב את הקשת שהורדה ניתן להחליף אותה [math]\displaystyle{ C=(v_0,\dots,v_{n-1}) }[/math].) לכן לפי הרצאה יש לו לפחות [math]\displaystyle{ |V|-1 }[/math] קשתות ולכן [math]\displaystyle{ |V|-1\leq |E|-1 }[/math] ואחרי העברת אגפים נקבל את המבוקש.

טענה: [math]\displaystyle{ |E|\leq |V| }[/math]

הוכחה: נניח בשלילה כי [math]\displaystyle{ |V|+1\leq |E| }[/math]

נסתכל על הגרף [math]\displaystyle{ G'=(V,E\setminus \{v_{n-1},v_n\}) }[/math] הוא בעל [math]\displaystyle{ |V| \leq|E|-1 }[/math] קשתות אך הרסנו את המעגל היחידי שהיה ב G אבל לפי תרגיל ממקודם אם מספר הצלעות גדול שווה ממספר הקודקודים יש בו מעגל. סתירה.

תרגיל

א. מהו הקוטר המקסימלי של גרף קשיר עם [math]\displaystyle{ n }[/math] קודקודים?

ב. מהו המספר המינימלי של קשתות בגרף עם [math]\displaystyle{ n }[/math] קודקודים וקוטר 2?

פתרון:

א. [math]\displaystyle{ n-1 }[/math]. לא יכול להיות יותר כי הקוטר מוגדר כמרחק המקסימלי בין קודקודים, ומרחק הוא אורך המסלול הקצר, ומסלול קצר לא מכיל מעגלים, ולכן מכיל לכל היותר [math]\displaystyle{ n }[/math] קודקודים, ולכן לכל היותר [math]\displaystyle{ n-1 }[/math] קשתות. גרף קו הוא עם קוטר [math]\displaystyle{ n-1 }[/math] כי זה המרחק בין הימני ביותר לשמאלי ביותר, לכן זה הקוטר המקסימלי.

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