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

* אם לצומת <math>\,v</math> מתקיים <math>\,\deg^+(v)=0</math>, הצומת נקרא '''מקור'''. זאת מאחר שהואוהוא מהווה מקור לכל הקשתות היוצאותהעוברות ממנודרכו.

ניתן להגדיר פורמלית את דרגתו של צומת <math> \ v_i</math> בגרף בלתי-מכוון ללא קשתות מקבילות <math>\ G=(V, E)</math> כש־<math>\ V</math> הוא אוסף הצמתים ו־<math>\ E</math> הוא אוסף הקשתות, באופן הבא:

<center><math>\,\deg(v_i) = \left|\left\{v_j\}|in V: e_\{ijv_i,v_j\} \in E\right\}\right|</math></center>

כלומר, הגודל של קבוצת כל הצמתים <math> \ v_j</math> שקיימת קשת בינם לבין <math> \ v_i</math>.

באופן דומה ניתן להגדיר את דרגות הכניסה והיציאה בגרף מכוון ללא קשתות מקבילות:

<center><math>\,\deg^+(v_i) = |\{v_j\}| : e_{ji} \in E \qquad \,\deg^-(v_i) = |\{v_j\}left| : e_{ij} \in E</math></center>left

'''נוסחת סכום הדרגות''' קובעת שסכום הדרגות של כל הצמתים בגרף שווה ל: <math>\sum_{v \in V} \deg(v) = 2|E|</math>, זאת מאחר שלכל קשת יש שני קצוות, וכך היא תורמת 2 לסכום הדרגות בגרף. מסקנה מכך היא שבכל גרף יש מספר זוגי של צמתים מדרגה אי-זוגית.