דרגה (תורת הגרפים)

דרגה של צומת היא כמה קשתות נוגעות בו. כותבים את זה \deg(v). גרף שבו לכל הצמתים יש אותה דרגה קוראים לו k-רגולרי. בגרף בלי כיוונים נספר כמה קשתות נוגעות בצומת. לולאה היא קשת שמחוברת לצומת עצמו. לולאה נספרת פעמיים. בגרף עם כיוונים לכל קשת יש "ראש" ו"זנב". לכן מחשבים שני סוגי דרגות. דרגת הכניסה ...