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

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