נוסחת אוילר (תורת הגרפים) – הבדלי גרסאות

←‏הוכחת המשפט: ניסוח חסר של הליך הורדת הקשתות
מ (בוט: מעביר קישורי בינויקי לויקינתונים - d:q516403)
(←‏הוכחת המשפט: ניסוח חסר של הליך הורדת הקשתות)
 
==הוכחת המשפט==
דרך קלה להיווכח שהמשפט נכון הוא בשיטה של מחיקת קשתות. נמחק את קשתות הגרף בזו אחר זו. בתחילהתחילה נמחק קשתות המשתתפות במעגל (נשים לב שמחיקה כזו אינה פוגעת בקשירות הגרף). כל קשת שנמחקהכזו מפרידה בין שתי פאות (כזכור גם האזור מחוץ לגרף נחשב פאה), ולכן מחיקת הקשת מקטינה את מספר הקשתות באחת וגם את מספר הפאות. נשים לב שהאזור שנמצא מחוץ לכל הגרף נחשב גם הוא כפאהבאחת. לאחר שנותרהשלא פאהנותר יחידה, ולא ניתן לאחד יותרמעגל, הגרף שנותרשמתקבל הוא [[עץ (תורת הגרפים)|עץ]], ומחיקהויש שלפאה כלאחת קשתבלבד. גםכעת מקטינהנמחק אתבזה מספראחר זה עלה עם הקשת המחברת אותו. באופן זה אנו מוחקים צומת אחד וקשת אחת הצמתיםבכל באחדפעם. מכאן שבסוף תהליך המחיקה מספר הקשתות שנמחקו שווה למספר הפאות + מספר הצמתים שנמחקו. לבסוף נשארים עם צומת בודד ופאה בודדת, ומכאן מתקבלת הנוסחה.
 
== נוסחת אוילר לפאונים ==
משתמש אלמוני