Königsberg vatandaşlarının çoğu Pazar öğleden sonralarını şehirde dolaşarak geçiriyordu. Şehrin içinden Pregel nehri geçmekteydi ve nehrin ortasında iki adacık oluşmuştu. Nehir boyunca adaları birbirine ve anakaraya bağlayan yedi köprü vardı. Dolaşmaya çıkanlar her köprüyü yalnızca bir kez geçerek şehrin içinde yürüyebilir mi? Bu soru zamanla, Königsberg Köprüsü problemi olarak bilinmeye başlandı. İşin içine Euler karışına kadar bulmaca şehir sakinlerini ve matematikçileri oldukça oyaladı. Euler’in ortaya koyduğu çözüm ise, günümüzde Graf teorisi ya da çizge kuramı olarak bilinen bir matematik dalının doğmasına neden oldu. Öncelikle akla gelebilecek bir soruyu soralım.

Carl LeonhardEuler o zamanlarda, Königsberg’in yaklaşık 130 km. batısında bulunan Prusya’da bir şehir olan Danzig’in belediye başkanıydı. 1736’da Euler’e yazılan bir mektup, Königsberg Köprüsü probleminden haberdar olmasını sağladı. Euler’in ise bu probleme bir cevap vermesi sadece 4 gününü alacaktı. Euler’in çözümü için tüm alakasız bilgileri göz ardı etti. Çözüm için Königsberg haritası da gerekli değildi. Bize gereken sadece Königsberg köprüleriydi. Bu yüzden Euler köprüleri çizgiler, adalar ve anakarayı ise daireler şeklinde çizdi. Bir köprüden diğerine ancak her ikisi de aynı daireye bağlıysa yürüyebilirsiniz.

Königsberg kentinde her köprüyü tam olarak bir kez geçerek dolaşmanın imkansız olduğunu gösteren Königsberg Köprüsü Probleminin çözümü, 1735’te Euler tarafından Petersburg Akademisi üyelerine sunuldu. Çözümü basitçe şu şekilde aktarabiliriz. Böyle bir yürüyüşü gerçekleştirmek isteyen kişinin iki seçeneği vardır. Seçeneklerinden ilki bir tur yapmaktır yani başladığı noktada yürüyüşünün bitirmektir. Diğer seçenek ise bir noktada yürüyüşe başlayıp başka bir yerde yürüyüşü tamamlamaktır. Önemli olan tek bir şey vardır. O da her köprüyü sadece bir kez geçmek. Aynı köprüden gidip geri dönmek bu nedenle mümkün değildir. Eğer ilk senaryodaki gibi bir yürüyüş yapar yani bir tur atarsanız yola çıktığınız kara parçasına bağlı en az iki köprü olması gerekir. Birini giderken diğerini de dönerken kullanacaksınız. Yani köprü sayısı çift olmalıdır. Grafik üzerinde düşünürsek de her daireye çift sayıda çizgi bağlı olmalıdır.

Farklı bir başlangıç ​​ve bitiş noktası olan ikinci senaryodaki gibi bir yürüyüşte, başlangıç ​​noktasında bir köprü ve bitiş noktasında bir köprü vardır. Yürüyüşünüz esnasında da bir köprüden kara parçasına ayak basar, diğer köprüden de çıkarak yolunuza devam ederseniz. Bu durumda eğer A noktasından B noktasına gidiyorsanız yola A noktasındaki köprüden geçerek çıkmalı sonra bir giriş bir çıkış iki ucu olan bir kara parçasından geçmeli ve son olarak bir köprü ile B noktasında varmalısınız. Şimdi yukarıdaki grafiğe göz atın. Her ada parçasına bağlı tek sayıda çizgi olduğunu göreceksiniz. İşte bu nedenle Königsberg şehrinin içinde her köprüden bir kere geçerek dolaşmak imkansızdır.

Euler bu düşüncesini elbette biraz daha karmaşık biçimde dile getirdi. İki veya daha fazla düğüm içeren ( düğüm= daire) tüm graflar için geçerli kuralı şu şekilde belirledi. Her kenardan ( çizgiden) sadece bir kez geçen bir Euler yolu iki biçimde mümkündür. İlki tek dereceli ( derece: Daireden çıkan çizgi sayısı) tam olarak iki düğümün bulunmasıdır. Diğer düğümler de çift dereceli olmalıdır. Burada başlangıç noktası tek dereceli düğümlerden biri, bitiş noktası da tek dereceli düğümlerden diğeri olmalıdır. İkinci durumda da tüm düğümler çift dereceli olmalıdır. Bu durumda Euler yolu başladığı noktada bitecektir.

Tüm bunların günlük yaşamınızda pek işe yaramadığını düşünebilirsiniz. Ancak oyunların olasılık teorisinin gelişmesine yol açması gibi, graf yani çizge teorisi de bu bilmeceyle başladı. Bu fikir artık Google Haritalar ile rotaları planlamak için kullanılıyor.