בעיר קניגסברג הפרוסית — היום קלינינגרד — זורם נהר הפְּרֶגֶל, ובתוכו שני איים. בין שתי גדות הנהר לשני האיים נמתחו במאה ה-18 שבעה גשרים.

תושבי העיר ניסו שוב ושוב לפתור חידה אחת שהעסיקה אותם בשבתות: האם אפשר לצאת לטיול בעיר, לעבור על כל אחד משבעת הגשרים בדיוק פעם אחת, ולא לעבור על אף גשר פעמיים?

איש לא הצליח — אך גם איש לא הצליח להסביר מדוע. בשנת 1736 הכריע את השאלה המתמטיקאי השווייצרי לאונרד אוילר.

מה הייתה תשובתו, ובעיקר — כיצד הוכיח אותה?

רמז דק

אורכם של הגשרים, גודל האיים וצורת הרחובות אינם משנים דבר. מה שקובע הוא רק נתון אחד: כמה גשרים יוצאים מכל יבשה.

רמז עבה

דמיינו כל יבשה כנקודה, וכל גשר כקו המחבר שתי נקודות. אם הגעתם ליבשה שאינה נקודת ההתחלה ואינה נקודת הסיום — אתם חייבים גם לצאת ממנה. מה זה מכתיב לגבי מספר הגשרים היוצאים ממנה?

פתרון

אוילר הוכיח שהמסלול אינו אפשרי כלל.

הרעיון: כל ביקור ביבשה שאינה ההתחלה או הסוף מורכב מזוג — גשר שבו נכנסתם וגשר שבו יצאתם. לכן מספר הגשרים היוצאים מיבשה כזו חייב להיות זוגי. רק לשתי יבשות מותר שיהיה מספר גשרים אי-זוגי: זו שממנה יוצאים בהתחלה וזו שבה מסיימים.

בקניגסברג יצאו מארבע היבשות 3, 3, 3 ו-5 גשרים — כלומר כל ארבעתן אי-זוגיות. מכיוון שארבע גדול משתיים, אין ולא יכול להיות מסלול כזה. לא מדובר בכישלון של הנסיינים אלא בבלתי אפשרי מתמטית.

המאמר שבו פרסם אוילר את הפתרון נחשב היום למאמר הראשון בתורת הגרפים ולאחד ממקורותיה של הטופולוגיה. מסלול העובר על כל צלע בדיוק פעם אחת נקרא מאז ועד היום "מסלול אוילר".