שינויים

'''הערה:''' אפשר להכליל את התרגיל, ולהפוך אותו לתרגיל על קוטר של גרף: יהי <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}+1</math>, ולכן יש בגרף לפחות <math>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>.