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

Euler Circuits and The K¨onigsberg Bridge Problem http://www.math.nmsu.edu/hist_projects/Euler-Barnett.pdf]</ref>.

 

 

הוכחה: נניח קיים גרף קשיר שדרגות כל קודקודיו זוגיות. נמצא מעגל אוילר - יוצאים מצומת כלשהו במקרה של מעגל, ומתקדמים בגרף באופן שרירותי, עד אשר "נתקעים" זה יקרה רק כשחוזרים לצומת שממנו התחלנו. כעת מסתכלים על החלקים שטרם כיסינו מהגרף. בכל אחד מהם יש אפס צמתים בעלי דרגה אי זוגית. אם כך, מה שעושים הוא כך: בוחרים צומת כלשהו על המסלול שכבר סימנו, שיוצאות ממנו קשתות שטרם הלכו בהן, ומחפשים מעגל שמתחיל ונגמר בו. אם נתקעים גם במקרה זה, ממשיכים לחפש "תיקון", בדרך [[רקורסיה|רקורסיבית]]. משמצאנו מעגל אוילרי, ניתן להוסיף אותו למסלול המקורי שלנו - במקום שנמשיך בקשת שבחרנו מלכתחילה, נכנס קודם למעגל החדש שבנינו, ואחרי שנסיים לעבור בו נחזור לצומת שממנה התחלנו, ואפשר להמשיך משם כרגיל במסלול המקורי שלנו.