Jalur dan sirkuit Euler

Graf terhubung bila dari setiap simpul ada lintasan ke setiap simpul lain. Sirkuit Euler adalah perjalanan yang melewati setiap sisi tepat sekali lalu kembali ke simpul awal. Jalur Euler juga melewati setiap sisi tepat sekali, tetapi berakhir di simpul yang berbeda dari simpul awal. Masalah ini muncul saat merencanakan rute yang harus menyusuri setiap ruas jalan: penyapu jalan, pembaca meteran, petugas pos, atau mesin pemotong yang harus menelusuri setiap garis tanpa mengulang.

Euler menemukan syaratnya dari derajat simpul. Graf terhubung punya sirkuit Euler bila dan hanya bila setiap simpulnya berderajat genap. Graf terhubung punya jalur Euler yang bukan sirkuit bila dan hanya bila tepat dua simpulnya berderajat ganjil, dan jalur itu harus dimulai di salah satu simpul ganjil lalu berakhir di simpul ganjil lainnya. Alasannya: setiap kali perjalanan melewati sebuah simpul, perjalanan itu masuk lewat satu sisi dan keluar lewat sisi lain, sehingga sisi-sisinya terpakai berpasangan. Graf jembatan Königsberg punya empat daratan yang semuanya berderajat ganjil, sehingga tidak ada jalur maupun sirkuit Euler di sana. Bila sirkuit tetap dibutuhkan, sisi ganda ditambahkan di antara simpul-simpul ganjil sampai semua derajat genap; cara ini disebut eulerisasi, dan setiap sisi tambahan berarti satu ruas yang dilewati dua kali.