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

תוכן עניינים

1 הגדרות בסיסיות
- 1.1 משפט (לחיצת הידיים)
  - 1.1.1 תרגיל
- 1.2 הגדרות נוספות
  - 1.2.1 בניה
2 תרגילים נוספים

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

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

הקבוצה $V$ היא קבוצת הקדקודים של הגרף, והקבוצה $E$ היא קבוצת הקשתות/צלעות של הגרף.

הגדרה: הסדר של גרף $G=(V,E)$ הוא $|V|$ . גרף יקרא סופי אם הסדר שלו סופי, וקבוצת הקשתות $E$ סופית.

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

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

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

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

בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- $\exists (v,v) \in E$ .
צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (כי $E$ קבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.

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

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

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

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

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

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

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

תרגיל

נאמר כי גרף $G=(V,E)$ הוא $k$ -רגולרי אם הדרגה של כל קדקוד שווה ל- $k$ . למשל, משולש הוא גרף 2-רגולרי.

הוכח כי אם $k,n$ אי-זוגיים, לא קיים גרף $k$ -רגולרי מסדר $n$ .

הוכחה:

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

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

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

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

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

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

בניה

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

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

פתרון:

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

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

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

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

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

תרגיל

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

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

תרגיל

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

א. יש בגרף מסלול פשוט מאורך לפחות $\delta_G$ .

ב. יש בגרף מעגל פשוט מאורך לפחות $\delta_G+1$ .

פתרון

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

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

תרגיל

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

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

עבור $n=3$ הגרף הוא בהכרח משולש (לא יכולות להיות יותר מ-3 צלעות עבור 3 קדקודים) ואכן יש מעגל.

נניח כי הטענה נכונה עבור $n$ ונוכיח עבור $n+1$ . יהי $G$ בעל $n+1>3$ קדקודים ו- $m\ge n+1$ צלעות.

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

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

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

תרגיל

יהי $G$ גרף מסדר $n>1$ . הוכח שקיימים 2 קדקודים בעלי אותה דרגה.

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

אם קיים קדקוד מדרגה $n-1$ , אז הוא מחובר לכולם ולכן אין קדקוד מדרגה אפס. במקרה זה מתקיים

$\operatorname{Im}(f) \subseteq \{1,\dots n-1\}$ .

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

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

תרגיל

יהיה $G=(V,E)$ גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי $G$ קשיר.

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

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

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

תרגיל

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

פתרון: לפי תרגיל קודם קיים $v\in V$ כך שדרגתו לכל היותר 1 (אחרת לכל הקדקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם).

נמשיך באינדוקציה על $n$ , מספר הקדקודים בגרף.

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

כעת נניח כי הטענה נכונה עבור $n\geq 2$ . נוכיח את הטענה עבור $n+1$ .

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

אם $v$ שכן של $v_1$ אזי $v,v_2$ בעלי דרגה לכל היותר 1.
אם $v$ שכן של $v_2$ אזי $v,v_1$ בעלי דרגה לכל היותר 1.
אם $v$ שכן של $v_1,v_2$ - סתירה כי הדרגה של $v$ היא 1 לכל היותר.
אם $v$ לא שכן של $v_1,v_2$ אזי $v,v_1,v_2$ בעלי דרגה לכל היותר 1.

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

תרגיל

הוכח/הפרך:

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

פתרון:

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

תרגיל

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

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

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

תרגיל

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

פתרון: נסמן את המעגל היחידי ב G ב $C=(v_0,\dots,v_n)$ .

טענה: $|V|\leq |E|$

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

טענה: $|E|\leq |V|$

הוכחה: נניח בשלילה כי $|V|+1\leq |E|$

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

תרגיל

א. מהו הקוטר המקסימלי של גרף קשיר עם $n$ קודקודים?

ב. מהו המספר המינימלי של קשתות בגרף עם $n$ קודקודים וקוטר 2?

פתרון:

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

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

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

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

תוכן עניינים

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

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

תרגיל

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

בניה

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

תרגיל

תרגיל

פתרון

תרגיל

תרגיל

תרגיל

תרגיל

תרגיל

תרגיל

תרגיל

תרגיל

תפריט הניווט

כלים אישיים

גרסאות שפה

מרחבי שם

חיפוש

עוד

צפיות

ניווט

כלים

@@ שורה 2: / שורה 2: @@
 = הגדרות בסיסיות =
-'''הגדרה''' יהיה <math>V</math> קבוצה לא ריקה. יהא <math>E</math> קבוצה המכילה זוגות לא סדורים מאיברי <math>V</math>
+'''הגדרה''': '''גרף''' <math>G</math> מעל קבוצה <math>V</math> הוא זוג סדור <math>G=(V,E)</math> כאשר <math>E \subseteq V\times V</math> - כלומר קבוצה המכילה זוגות סדורים מאיברי <math>V</math>.
-אזי <math>G=(V,E)</math> נקרא גרף לא מכוון.
-חושבים על <math>V</math> כקודקודים של הגרף ועל <math>E</math> כקשתות/צלעות של הגרף. את האיברים ב <math>E</math>
+הקבוצה <math>V</math> היא קבוצת ה'''קדקודים''' של הגרף, והקבוצה <math>E</math> היא קבוצת הקשתות/צלעות של הגרף.
-נהוג לרשום כקבוצה <math>\{v,w\}\in E</math> (בגלל שזה זוגות לא סדורים)
+'''הגדרה''': הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי, וקבוצת הקשתות <math>E</math> סופית.
-דוגמא: <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math>  מייצג משולש.
+'''הגדרה''': גרף <math>G</math> ייקרא '''לא מכוון''' אם היחס <math>E</math> הוא סימטרי, כלומר אין משמעות לכיוון הצלע. אחרת הגרף ייקרא מכוון. בגרף לא מכוון, אין משמעות לכיוון הצלע, ולכן לעתים מסמנים <math>(u,v)</math> בתור <math>\{u,v\}</math>.
+'''דוגמא''': <math>V=\{1,2,3\}, E=\Big\{\{1,2\},\{2,3\},\{1,3\}\Big\}</math>  מייצג משולש. הסדר שלו הוא 3, כמספר הקדקודים במשולש. זהו גרף סופי.
-'''הגדרה''' הסדר של גרף <math>G=(V,E)</math> הוא <math>|V|</math>. גרף יקרא סופי אם הסדר שלו סופי (וגם <math>E</math> סופית)
+'''דוגמא''': נביט בקבוצה <math>\mathbb{Z}\times\mathbb{Z}</math>, ובגרף <math>G</math> מעליה, בו מחברים בין כל שני קדקודים במרחק 1 זה מזה - מתקבלת רשת אינסופית. זהו גרף אינסופי, בו לכל קדקוד יש ארבעה שכנים.
+'''הערה''': שימו לב שמהניסוח לעיל נובע-
+# בגרף יכולה להיות קשת מקדקוד אל עצמו (לולאה). זה שקול ל- <math>\exists (v,v) \in E</math>.
+#צלע בין שני קדקודים יכולה להופיע אך ורק פעם אחת (כי <math>E</math> קבוצה). בפועל, יש גרפים שבהם מופיעה יותר מצלע אחת בין שני קדקודים (למשל שתי לולאות סביב נקודה). נסו לחשוב איך להגדיר את זה פורמלית.
-אנחנו נעסוק בגרפים לא מכוונים בלי לולאות כלומר המקיימים <math>\forall v\in V : \{v,v\}\not\in E</math> ובלי צלעות כפולות, כלומר לא מופיע פעמיים <math>\{v,w\}</math> ב <math>E</math>. בנוסף הגרפים שלנו יהיו סופיים.
+'''הבהרה: אנחנו נעסוק בגרפים סופיים, לא מכוונים, בלי צלעות כפולות ובלי לולאות'''.
+'''הגדרה''' יהיה <math>G=(V,E)</math>. נאמר כי <math>v,w\in V</math> '''שכנים''' אם <math>(v,w)\in E</math>. במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>)
-'''הגדרה''' יהיה <math>G=(V,E)</math>  נאמר כי <math>v,w\in V</math> שכנים אם <math>\{v,w\}\in E</math>.
+את קבוצת השכנים של <math>u</math> מסמנים <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math>.
-במקרה זה נאמר כי הצלע <math>\{v,w\}\in E</math> חלה ב <math>w</math> (או חלה ב <math>v</math>)
+ה'''דרגה''' של <math>u</math>, המסומנת <math>\text{degree}(u)</math>, היא מספר הצלעות החלות ב <math>u</math>, כלומר <math>|\Gamma(u)|</math>.
-את קבוצת השכנים של <math>u</math> מסמנים כ <math>\Gamma(u)=\{v\in V \; :\; \{v,u\}\in E\}</math>
-הדרגה של <math>u</math> (סימון: <math>\text{degree}(u)</math>)היא מספר הצלעות החלות ב <math>u</math> או לחילופין <math>|\Gamma(u)|</math>
+'''דוגמא:''' במשולש, כל 2 קדקודים שכנים. כל קדקוד מדרגה 2: השכנים של כל קדקוד הם שני הקדקודים האחרים.
-בדוגמא של המשולש - כל 2 קודקודים שכנים. כל קודקוד מדרגה 2. השכנים של קודקוד מספר 1 הוא קודקוד 2 + קודקוד 3.
+==משפט (לחיצת הידיים)==
+יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}\text{degree}(v)=2|E|</math>.
-==משפט''' (לחיצת הידיים)==
-יהי <math>G=(V,E)</math> גרף לא מכוון. אזי <math>\sum_{v\in V}\text{degree}(v)=2|E|</math>.
 === תרגיל ===
-הגדרה גרף <math>G=(V,E)</math> יקרא k-רגולרי אם כל הדרגה של כל קודקוד היא k (בדיוק)
+נאמר כי גרף <math>G=(V,E)</math> הוא <math>k</math>-'''רגולרי''' אם הדרגה של כל קדקוד שווה ל-<math>k</math>. למשל, משולש הוא גרף 2-רגולרי.
-הוכח כי לא קיים גרף k-רגולרי מסדר n אם n,k אי-זוגיים
+הוכח כי אם <math>k,n</math> אי-זוגיים, לא קיים גרף <math>k</math>-רגולרי מסדר <math>n</math>.
 הוכחה:
-אם n,k אי-זוגיים אז לפי משפט לחיצת הידיים <math>2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k</math>.
+לפי משפט לחיצת הידיים <math>2|E|=\sum_{v\in V}\text{degree}(v)=n\cdot k</math>. לכן <math>nk</math> זוגי, ולכן <math>k</math> זוגי או <math>n</math> זוגי.
-אבל מכפלה של מספרים אי זוגיים היא אי-זוגית. סתירה
+==הגדרות נוספות==
+יהי <math>G=(V,E)</math> גרף לא מכוון. סדרת קדקודים (סדורה) <math>(v_0,v_1,\dots,v_n)</math> נקראת '''מסלול''' אם <math>\forall i : \{v_i,v_{i+1}\}\in E</math> וגם כל הצלעות שונות - כלומר לכל <math>i\neq j</math> מתקיים <math>(v_i,v_{i+1}) \neq (v_j,v_{j+1})</math>.
-==עוד הגדרות:==
+מסלול יקרא '''פשוט''' אם כל הקדקודים <math>(v_0,v_1,\dots,v_n)</math> שונים זה מזה, פרט אולי ל <math>v_0=v_n</math>, ובמקרה זה המסלול נקרא '''מעגל'''. אורך המסלול <math>(v_0,v_1,\dots,v_n)</math> הוא <math>n</math>, והנקודות <math>v_0</math> ו-<math>v_n</math> נקראות '''נקודות ההתחלה והסיום''' של המסלול.
-יהי <math>G=(V,E)</math> גרף לא מכוון. סדרת קודקודים (סדורה) <math>(v_0,v_1,\dots,v_n)</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>\forall i : \{v_i,v_{i+1}\}\in E</math> וגם כל הצלעות שונות - כלומר לכל <math>i\neq j</math> מתקיים כי <math>(v_i,v_{i+1} \neq (v_j,v_{j+1}))</math>
-מסלול יקרא פשוט אם כל הקודקודים <math>(v_0,v_1,\dots,v_n)</math> שונים זה מזה, פרט אולי ל <math>v_0=v_n</math>
+ה'''קוטר''' של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין זוגות קדקודים - כלומר <math>\operatorname{diam}(G)=\max_{u,v\in V}{d(v,u)}</math>
-מעגל הוא מסלול פשוט המקיים <math>v_0=v_n</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_0,v_1,\dots,v_n)</math> הוא <math>n</math>
+'''תרגיל''': הוכח כי זהו יחס שקילות.
-<math>(v_0,v_1,\dots,v_n)</math> הינו מסלול מ <math>v_0</math> ל <math>v_n</math>
+'''פתרון''':
+# ''רפלקסיבי'' - לכל קדקוד <math>v</math>, המסלול <math>(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> 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>.
-'''הגדרה'''
+'''הגדרה''' מחלקות השקילות של יחס זה נקראים רכיבי קשירות.
-המרחק בין <math>v,u\in V</math> הוא המסלול עם אורך מינמאלי בין הקודקודים. (סימון <math>d(u,v)</math> או <math>d_G(u,v)</math> ).
+הגדרה: G יקרא קשיר אם בין כל שני קודקודים יש מסלול. זה שקול לכך שיש רכיב קשירות או באופן שקול <math>\forall v\in V:[v]_{\to}=V</math>
-אם אין מסלול בין <math>v,u\in V</math> נסמן <math>d(u,v)= \infty</math>
+'''דוגמא''': ציור חביב לפי דעת המתרגל.
-הקוטר של גרף <math>G=(V,E)</math> מוגדר כמרחק המקסימאלי בין 2 קודקודים . כלומר <math>\max_{u,v\in V}d(v,u)</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>\to </math> על <math>V</math> כך:
+==תרגיל==
+יהי <math>G=(V,E)</math> גרף, ונסמן <math>\delta_G=\underset{v\in V}{\min}\{deg(V)\}</math> את הדרגה המינימלית בגרף. נניח <math>\delta_G\geq 1</math>. הוכיחו:
-לכל <math> v,u\in V</math> מתקיים <math> v\to u</math> אמ"מ קיים מסלול מ<math>v</math> ל <math>u</math> (כלומר <math>d(v,u)<\infty </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>G=(V,E)</math> בעל <math>3\leq n</math> קודקודים.
-אם בגרף <math>n\leq m </math> צלעות אזי בגרף יש מעגל.
-הוכחה: באינדוקציה.
+ב. יהי <math>(v_1,v_2,\dots ,v_k)</math> מסלול פשוט מאורך מקסימלי. ראינו שכל שכני הראשון במסלול, ולכן מספיק לקחת את המסלול עד שמגיעים לאחרון השכנים, ואז לחזור חזרה ל <math>v_1</math> ולקבל מעגל פשוט מהאורך המתאים.
-עבור <math>n=3</math> אזי יש מדובר במשולש (לא יכול להיות יותר מ -4 צלעות ב-3 קודקודים) ואכן מתקיים כי יש מעגל.
+==תרגיל==
+יהי <math>G=(V,E)</math> גרף בעל <math>n\ge 3</math> קדקודים. ו-<math>m \ge n </math> צלעות. אזי בגרף יש מעגל.
-נניח כי הטכנה נכונה עבור <math>n</math> ונוכיח עבור <math>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> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.
+עבור <math>n=3</math> הגרף הוא בהכרח משולש (לא יכולות להיות יותר מ-3 צלעות עבור 3 קדקודים) ואכן יש מעגל.
-אפשרות 2: לכל קודקוד יש דרגה גדולה שווה 2. נבחר <math>v_0\in V</math> ונצא ממנו לאחד משכניו. מפה נמשיך למסלול רנדומאלי כך שאם הולכים מ <math>v\to u</math> הצעד הבא לא יהיה <math>u\to v</math> (זה אפשרי כי כל קודקוד יש לפחות 2 שכנים אז אם נכנסים אליו משכן א ניתן לצאת משכן ב). כיוון שיש מספר סופי של קודקודים נקבל חזרה על קודקוד בשלב כלשהוא. בפעם הראשונה שנקבל חזרה קיבלנו מעגל!
+נניח כי הטענה נכונה עבור <math>n</math> ונוכיח עבור <math>n+1</math>. יהי <math>G</math> בעל <math>n+1>3</math> קדקודים ו- <math> m\ge n+1</math> צלעות.
-== תרגיל ==
+''אפשרות 0'' - קיים קדקוד מדרגה 0 - כלומר אין לו שכנים. אז נביט בגרף בלי הקדקוד הזה, ומהנחת האינדוקציה נקבל שיש בו מעגל; זהו מעגל גם בגרף המקורי.
-יהי G גרף פשוט (ללא לולאות וללא צלעות מקבילות) מסדר <math>1<n</math>. הוכח שקיימים 2 קודקודים בעל אותה דרגה.
-הוכחה:
+''אפשרות 1'': קיים <math>v\in V</math> מדרגה 1. נוריד את הקדקוד הזה (ואת הצלע שחלה בו) ונקבל גרף חדש עם <math>n</math> קדקודים ו<math>m-1 \ge n </math> צלעות. לפי הנחת האינדוקציה קיים בו מעגל. מעגל זה קיים גם בגרף בו התחלנו.
-נבנה פונקציה <math>f:V\to \{0,1,\dots n-1\} </math> המוגדרת <math>v\mapsto deg(v)</math>.
+''אפשרות 2'': לכל קדקוד דרגה גדולה שווה 2. ולפי תרגיל קודם יש מעגל
-אם קיים קודקוד מדרגה n-1 אזי הוא מחובר לכולם ולכן אין קודקוד מדרגה אפס. במקרה זה נוכל להגדיר
+==תרגיל==
-<math>f:V\to \{1,\dots n-1\} </math>.
+יהי <math>G</math> גרף מסדר <math>n>1</math>. הוכח שקיימים 2 קדקודים בעלי אותה דרגה.
-אם אין קודקוד כזה אז נוכל להגדיר <math>f:V\to \{0,1,\dots n-2\} </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>.
-בשני המקרים קיבלנו כי <math>#dom(f)=#V=n, #Im(f)=n-1</math> ולכן <math>f</math> אינה חח"ע.
+בשני המקרים קיבלנו כי <math>|\operatorname{dom}(f)|=|V|=n, |\operatorname{Im}(f)|\le n-1</math> ולכן <math>f</math> אינה חח"ע.
-כלומר קיימים <math>v_1\neq v_2</math> כך ש <math>f(v_1)=f(v_2)</math> כלומר בעלי דרגה שווה
+כלומר קיימים <math>v_1\neq v_2</math> כך ש <math>f(v_1)=f(v_2)</math> כלומר בעלי דרגה שווה.
-==תרגיל:==
-יהי גרף לא מכוון <math>G=(V,E)</math>. הוכח כי אם <math>\forall v\in V : \text{degree}(v)\geq 2</math> אז בגרף יש מעגל.
+==תרגיל==
+יהיה <math>G=(V,E)</math> גרף פשוט עם 100 קדקודים כך שדרגת כל קדקוד לפחות 50. הוכח כי <math>G</math> קשיר.
-הוכחה: בגרף יש יותר מ 2 קודקודים (אחרת לא יהיה להם 2 שכנים).
+'''פתרון''': יהיו <math>v,u\in V</math>. צריך להוכיח כי <math>[v]=[u]</math> (כך נסמן את רכיב הקשירות).
-לפי משפט לחיצת הידיים מתקיים <math>2|E|= \sum_{v\in V}\text{degree}(v)\geq \sum_{v\in V}2 =2|V|</math>
+נניח כי הם שונים, אזי ב<math>|[v]|,|[u]|\geq 51</math> ( הקודוקד + לפחות 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>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>v\in V</math> כך שדרגתו לכל היותר 1 (אחרת לכל הקדקודים יש דרגה לפחות 2 ואז יש מעגל לפי תרגיל קודם).
-נמשיך באינדוקציה על <math>n</math> מספר הקודקודים בגרף.
+נמשיך באינדוקציה על <math>n</math>, מספר הקדקודים בגרף.
-אם <math>n=2</math> אזי או שהגרף הוא 2 נקודות לא צלעות או 2 נקודות המחוברות בצלע. בכל מקרה 2 הנקודות של הגרף הם מדרגה קטנה שווה ל-1.
+אם <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\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_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).