מסלול אוילר – הבדלי גרסאות

נניח שקיים מסלול אוילר. אם תחילת המסלול וסופו חלים באותו קודקוד - זהו מעגל אוילר, ולכן יש 0 קודקודים אי זוגיים. נחבר את תחילתו וסופו ונקבל מעגל אוילר ולכן כל דרגות הקודקודים זוגיות. נשמיט את הצלע - יש לנו 2 קודקודים שדרגתם אי זוגית.

 

 

'''גרפים מכוונים:''' ב[[גרף מכוון]] [[תנאי הכרחי ומספיק]] לקיום מעגל אוילר הוא שהגרף יהיה [[גרף קשיר#רכיב קשיר היטב|קשיר היטב]] ובכל קודקוד דרגת הכניסה זהה לדרגת היציאה. בגרף מכוון יש אלגוריתם פולינומי לספירת מעגלי אוילר, תוך שימוש ב[[משפט קירכהוף]], אולם בגרף לא מכוון הבעיה היא שלמה ל{{משמאל לימין|[[Sharp-P|#P]]}} (כלומר בדומה לבעיית ה[[שידוך (תורת הגרפים)|שידוך המושלם בגרף]], זהו מקרה שבו בעיית ההכרעה היא ב[[P (סיבוכיות) |P]] אולם בעיית הספירה קשה){{הערה|1=Graham Brightwell, Peter Winkler: Counting Eulerian Circuits is #P-Complete. ALENEX/ANALCO 2005:259-262}}.