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

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