כל מה שרצית לדעת על מסלול אוילר:
מעגל אוילר: בגרף קשיר קיים מעגל אוילר אם ורק אם כל הדרגות זוגיות.
הוכחה: בהינתן גרף קשיר שדרגות כל צמתיו זוגיות, נראה איך למצוא מעגל אוילר.
נצא מצומת כלשהו ונתקדם בגרף באופן שרירותי, ללא חזרה על קשתות, עד אשר "נתקע", כלומר נגיע לצומת שאי אפשר לבחור ממנו קשת שעדיין לא נבחרה.
הטענה היא שזה יקרה רק כשנחזור לצומת שממנו התחלנו.
הסיבה היא שבכל שלב בבחירת המסלול, פרט לצומת ההתחלה והסיום במסלול הנבחר, לכל שאר הצמתים דרגה זוגית במסלול – מכיוון שעל כל כניסה לצומת יש יציאה ממנו.
אם נכנס לצומת כשסך כל דרגתו במסלול היא אי זוגית, הרי אי אפשר להתקע, כי מזוגיות הדרגה נובע כי תהיה קשת שעדיין לא השתמשנו בה.
לכן המסלול נתקע רק אם חוזרים לנקודת הפתיחה, כי זו הדרך היחידה שדרגת הצומת בסוף המסלול יכולה להיות זוגית.
כעת נסתכל על תת-הגרף המתקבל מהקשתות שעדיין לא כוסו.
בתת-הגרף הזה הדרגה בכל צומת היא זוגית, מכיוון שמהקשתות שהורדנו היה מספר זוגי בכל צומת.
נבחר צומת כלשהו על המסלול שכבר סימנו, שיוצאות ממנו קשתות שטרם נבחרו (חייבות להיות כאלה, אחרת הגרף אינו קשיר), ונחפש מעגל שמתחיל ונגמר באותו צומת.
אם נתקעים גם במקרה זה, ממשיכים לחפש "תיקון", בדרך רקורסיבית.
משמצאנו מעגל אוילר, ניתן להוסיף אותו למסלול המקורי שלנו – במקום שנמשיך בקשת שבחרנו מלכתחילה, נכנס קודם למעגל החדש שבנינו, ואחרי שנסיים לעבור בו נחזור לצומת שממנה התחלנו, ואפשר להמשיך משם כרגיל במסלול המקורי שלנו.
נניח שקיים מעגל אוילר.
מכיוון שזהו מעגל, המסלול לא מסתיים באף קודקוד.
לכן מספר הכניסות והיציאות מכל קודקוד שווה.
כתוצאה מכך שהמסלול עובר על כל צלע פעם אחת ויחידה מספר הכניסות והיציאות שווה ממש לדרגת הקודקוד.
נניח שיש כניסות בקודקוד מסוים, מכאן יש יציאות, ולכן דרגת הקודקוד הינה .
מכיוון ש- מספר טבעי, קבלנו דרגה זוגית.
מסלול אוילר: בגרף קשיר לא מכוון יש מסלול אוילר אם ורק אם יש בו 0 או 2 קודקודים עם דרגה אי זוגית.
הוכחה: נניח שקיימים רק 2 קודקודים עם דרגה אי-זוגית: a,b.
נוסיף לגרף קודקוד c שממנו יוצאות שתי צלעות, אחת ל-a והשנייה ל-b.
אנו עומדים בתנאי המשפט למעלה, לכן קיים מעגל אוילר המתחיל ומסתיים בקודקוד c.
נשמיט את הקודקוד c ונשאר לנו מסלול אוילר בין a ל b.
נניח שקיים מסלול אוילר.
אם תחילת המסלול וסופו חלים באותו קודקוד – זהו מעגל אוילר, ולכן יש 0 קודקודים אי זוגיים.
נחבר את תחילתו וסופו ונקבל מעגל אוילר ולכן כל דרגות הקודקודים זוגיות.
נשמיט את הצלע – יש לנו 2 קודקודים שדרגתם אי זוגית.
גרפים מכוונים: בגרף מכוון תנאי הכרחי ומספיק לקיום מעגל אוילר הוא שהגרף יהיה קשיר היטב ובכל קודקוד דרגת הכניסה זהה לדרגת היציאה.
בגרף מכוון יש אלגוריתם פולינומי לספירת מעגלי אוילר, תוך שימוש במשפט קירכהוף, אולם בגרף לא מכוון הבעיה היא שלמה ל#P (כלומר בדומה לבעיית השידוך המושלם בגרף, זהו מקרה שבו בעיית ההכרעה היא בP אולם בעיית הספירה קשה).