Lahirnya teori graf pertama kali diperkenalkan oleh Leonhard Euler seorang matematikawan berkembangsaan Swiss pada tahun 1736 melalui tulisan Euler yang berisi tentang upaya pemecahan masalah jembatan Konigsberg yang sangat terkenal di Eropa. Masalah jembatan Konigsberg adalah mungkin tidaknya melewati ketujuh jembatan yang ada di kota Konigsberg masing-masing tepat satu kali dan kembali lagi ditempat semula.Untuk memecahkan masalah itu, Euler memisalkan daratan yang dihubungkan dengan titik (vertex) dan jembatan dinyatakan dengan garis atau sisi (edge). Euler berkesimpulan bahwa tidak mungkin seseorang dapat melalui ketujuh jembatan itu,masing-masing satu kali dan kembali lagi ketempat semula. Sehingga kisah Jembatan Konisberg ini menjadi sejarah Lahirnya Teori Graf.
Gambar di atas merupakan representasi graf dari jembatan Konisberg, konon kabarnya, Penduduk kota Konisberg (sekarang bernama Kalilingrad, di Uni Soviet) sering berjalan – jalan pada saat libur ke kota tersebut. kemudian muncul suatu keinginan untuk dapat menikmati daerah tersebut dengan melalui ketujuh jembatan tepat satu kali yakni bermula dari satu tempat ( A, B, C atau D) dan kembali ketempat semula. Mereka berusaha untuk memperoleh rute yang sesuai dengan keinginan tersebut dan selalu mencoba menjalaninya. setelah mencoba berkali-kali ternyata mereka tidak berhasil kemudian mereka mengirim surat kepada Euler. Namun sesuai dengan tulasannya bahwa tidak mungkin seseorang dapat melalui ketujuh jembatan itu masing-masing satu kali dan kembali lagi ketempatt semula.
