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

[[תמונה:Konigsburg graph.png|שמאל|ממוזער|150px|גרף של [[הגשרים של קניגסברג]] - גרף זה איננו אוילרי ולכן לא קיים בו מסלול אוילרי.]]

[[תמונה:Labelled Eulergraph.svg||שמאל|ממוזער|150px|לכל צומת בגרף זה דרגה זוגית ולכן זהו גרף אוילרי, מעקב אלפביתי אחר הקשתות בגרף נותן מסלול אוילרי מעגלי.]]

 

אוילר הוכיח כי ב[[גרף קשיר]] קיים מעגל אוילריאני אם ורק אם יש בדיוק 0 צמתים בעלי [[דרגה (תורת הגרפים)|דרגה]] אי זוגית בגרף (כלומר, אין צומת שיוצא ממנו מספר אי זוגי של קשתות) וכי בגרף קיים מסלול אוילריאני אם ורק אם יש בדיוק 2 או 0 צמתים בעלי דרגה אי זוגית (במקרה של 0 צמתים בעלי דרגה אי זוגית מתקבל מעגל, משמע מעגל הוא מקרה פרטי של מסלול). בכל גרף עם מספר גדול יותר של צמתים בעלי דרגות אי זוגיות אין לא מסלול ולא מעגל אוילריאני (גרף בעל צומת אחד בעל דרגה אי זוגית לא יכול להתקיים). ההוכחה המלאה הראשונה לטענות אלה התפרסמה על ידי המתמטיקאי הגרמני קרל היירהולצר ב-1873 (לאחר מותו)<ref>[Early Writings on Graph Theory: