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

דוגמה של גרף מישורי: מספר הצמתים 8, מספר הקשתות 14, מספר הפאות 8, ואכן 8=14-8+2

בתורת הגרפים, נוסחת אוילר היא נוסחה מרכזית שמקורה בלאונרד אוילר. על פי הנוסחה, עבור גרפים מישוריים קשירים, ישנו קשר בין מספר הקשתות e, ומספר הצמתים v, ומספר הפאות f:

\ f=e-v+2

(הערה: גם השטח שמסביב לגרף נספר בתור פאה).

בזכות נוסחת אוילר, מאפיין אוילר של המישור מוגדר היטב, ושווה ל- $\chi =v-e+f=2\,\!$ .

ניתן להכליל את הנוסחה על ידי השמטת הדרישה שהגרף קשיר, ואז יתקיים

\ f=e-v+c+1

כאשר c הוא מספר רכיבי הקשירות.

הוכחת המשפט

דרך קלה להיווכח שהמשפט נכון הוא בשיטה של מחיקת קשתות בזו אחר זו.

תחילה נמחק קשתות המשתתפות במעגל (נשים לב שמחיקה כזו אינה פוגעת בקשירות הגרף). כל קשת כזו מפרידה בין שתי פאות (כזכור גם האזור מחוץ לגרף נחשב פאה), ולכן מחיקת הקשת מקטינה את מספר הקשתות באחת וגם את מספר הפאות באחת. לאחר שלא נותר מעגל, הגרף שמתקבל הוא עץ ויש פאה אחת בלבד.

כעת נמחק בזה אחר זה עלה עם הקשת המחברת אותו. באופן זה אנו מוחקים צומת אחד וקשת אחת בכל פעם. מכאן שבסוף תהליך המחיקה מספר הקשתות שנמחקו שווה למספר הפאות + מספר הצמתים שנמחקו. לבסוף נשארים עם צומת בודד ופאה בודדת, ומכאן מתקבלת הנוסחה.

נוסחת אוילר לפאונים

קובץ:Euler GDR stamp.jpg

בול מזרח גרמני לכבוד יום מותו ה־200 של אוילר. באמצע, ניתן לראות את נוסחת הפאון שלו

ניתן לתאר את השלד של פאון (המורכב מן הקודקודים והצלעות שלו) בגרף מישורי, על ידי מתיחת אחת הפאות (כל קודקוד יהווה צומת, וכל צלע תהווה קשת), ולכן נוסחת אוילר תקפה גם עבורם.

מנוסחת אוילר אפשר להסיק את המיון של הפאונים האפלטוניים, שהם פאונים שבהם כל הפאות חופפות לאותו מצולע משוכלל (נאמר, בן n צלעות), ובכל קודקוד נפגש אותו מספר פאות (נאמר, m). אם f הוא מספר הפאות, אז מספר הצלעות שווה ל- $e=f\cdot n/2$ , ומספר הקודקודים הוא $v=f\cdot n/m$ . על פי נוסחת אוילר $\ f+f\cdot {\frac {n}{m}}=f\cdot {\frac {n}{2}}+2$ , כלומר $\ f={\frac {4m}{2m-(m-2)n}}$ , וזה צריך להיות כמובן מספר טבעי. כאשר מוסיפים את הדרישה $\ n,m\geq 2$ , מתקבלים למשוואה הדיופנטית הזו רק חמישה פתרונות.