שינויים

יהא <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\\ \{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\\ \{v_{n-1},v_n\}</math> הוא בעל <math>|V| \leq|E|-1</math> קשתות אך הרסנו את המעגל היחידי שהיה ב G אבל לפי תרגיל ממקודם אם מספר הצלעות גדול שווה ממספר הקודקודים יש בו מעגל. סתירה.