สะพานทั้งเจ็ดแห่งเมืองเคอนิชส์แบร์ค
ในศตวรรษที่ 18 ผู้คนในเมืองเคอนิชส์แบร์ค (Königsberg) ขบคิดปริศนาข้อหนึ่งอยู่นาน แม่น้ำพรีเกล (Pregel) ไหลผ่านเมืองและแยกเป็นเกาะสองเกาะ มีสะพานข้ามแม่น้ำไปยังเกาะต่าง ๆ รวมเจ็ดสะพาน ในการเดินเล่นวันอาทิตย์ครั้งเดียว จะเดินข้ามสะพานทุกสะพาน โดยข้ามแต่ละสะพานเพียงครั้งเดียวได้หรือไม่ ลองดูว่าสะพานข้ามแม่น้ำตั้งอยู่อย่างไร:
เป็นไปได้หรือไม่ที่จะเริ่มเดินจากที่ใดที่หนึ่ง แล้วข้ามสะพานทุกสะพาน สะพานละครั้งเดียว ลองดูก่อน เริ่มจากมุมซ้ายล่าง เดินขึ้นไปด้านบน แล้วค่อย ๆ ไปทางขวา ดังนี้:
จะเห็นว่าข้ามสะพานได้หกจากเจ็ดสะพาน พลาดไปหนึ่งสะพาน ลองเส้นทางอื่น…
ข้ามสะพานของเมืองเคอนิชส์แบร์คได้เพียงหกจากเจ็ดสะพานอีกแล้ว ดูเหมือนว่าการเดินครั้งเดียวให้ข้ามทุกสะพาน สะพานละครั้งเดียว จะเป็นไปไม่ได้ วันหนึ่งนักคณิตศาสตร์ชื่อดัง เลออนฮาร์ด ออยเลอร์ (Leonhard Euler) ได้พบกับปัญหานี้ ที่จริงคำว่าชื่อดังยังน้อยไป ออยเลอร์เป็นตำนานของคณิตศาสตร์ ถึงขั้นที่จำนวน eก็ตั้งชื่อตามเขา (จำนวนออยเลอร์) ออยเลอร์ตั้งใจจะไขปริศนานี้ให้ได้ เขาเริ่มจากตั้งชื่อเกาะและส่วนต่าง ๆ ของเมืองที่มีสะพานเชื่อมถึง:
จากนั้นออยเลอร์ให้เหตุผลดังนี้ ถ้าเกาะใดมีสะพานเชื่อมถึงเป็นจำนวนคู่ ก็เดินข้ามสะพานเหล่านั้นได้หมดในการเดินครั้งเดียว ไม่ว่าจะเริ่มที่ใด กล่าวคือ ข้ามสะพานหนึ่งเข้าเกาะ แล้วข้ามอีกสะพานหนึ่งออกไป จำนวนสะพานที่ยังเหลือต้องข้ามจึงลดลงสอง การจะเข้าเกาะทางสะพานหนึ่งและออกทางอีกสะพานหนึ่งต้องใช้สะพานสองสะพาน ถ้าเกาะมีสะพานหกสะพาน ก็จะไปถึงเกาะนั้นสามครั้ง ตัวอย่างเช่น สมมติว่าเกาะ B มีสะพานสี่สะพานดังนี้:
ในกรณีนี้เดินครั้งเดียวก็ข้ามได้ทุกสะพาน ไม่ว่าจะเริ่มที่ใด ลองทำดู ในรูปแสดงเส้นทางไว้หนึ่งเส้นทาง แต่ถ้าเกาะ B มีสะพานจากเกาะ D เพิ่มอีกหนึ่งสะพาน:
จะเห็นว่าเส้นทางที่เลือกไว้ไม่ทำให้ข้ามทุกสะพานได้สะพานละครั้งเดียว ต้องข้ามสะพานใดสะพานหนึ่งกลับไปที่เกาะ B แล้วจึงข้ามไปเกาะ D ได้ แต่เราเลือกเส้นทางอื่นได้ ถ้าเริ่มเดินจากเกาะ B ก็จะข้ามทุกสะพานได้สะพานละครั้งเดียว:
เส้นทางนี้เริ่มที่เกาะ B ขึ้นไปยังพื้นที่ A แล้วข้ามสะพานกลับมาที่ B ไปยังพื้นที่ C แล้วกลับมาที่เกาะ B และสุดท้ายไปที่เกาะ D ดังนั้นถ้าเริ่มที่เกาะที่มีสะพานเป็นจำนวนคี่ ก็จะข้ามสะพานทุกสะพานของเกาะนั้นได้สะพานละครั้งเดียว หรือจะเดินในทางกลับกันก็ได้ คือเริ่มที่เกาะ D แล้วไปจบที่เกาะ B
ออยเลอร์จึงสังเกตว่า การจะข้ามทุกสะพานได้สะพานละครั้งเดียว ทุกเกาะต้องมีสะพานเป็นจำนวนคู่ หรือมีเกาะที่มีสะพานเป็นจำนวนคี่ได้สองเกาะ โดยเริ่มเดินที่เกาะหนึ่งที่มีสะพานเป็นจำนวนคี่ และไปจบที่อีกเกาะหนึ่ง เกาะอื่น ๆ ทั้งหมดต้องมีสะพานเป็นจำนวนคู่ ถ้ากลับมาดูสะพานเจ็ดสะพานเดิมของเมืองเคอนิชส์แบร์ค:
จะเห็นว่าทุกเกาะมีสะพานเป็นจำนวนคี่ เกาะ A มี 3 สะพาน B มี 5 สะพาน C มี 3 สะพาน และ D ก็มี 3 สะพาน ปริศนานี้จึงไม่มีคำตอบ การเดินเล่นวันอาทิตย์ครั้งเดียวให้ข้ามสะพานทั้งเจ็ด สะพานละครั้งเดียว เป็นไปไม่ได้ แต่ถ้ารื้อสะพานใดสะพานหนึ่งออก ปริศนาก็จะมีคำตอบทันที เช่น รื้อสะพานหนึ่งระหว่างเกาะ B และ C ออก:
จะเห็นว่าตอนนี้เกาะ B มีสะพาน 4 สะพาน และเกาะ C มีสองสะพาน ส่วนเกาะ A และ D มีจำนวนสะพานเท่าเดิม จึงมีเกาะที่มีสะพานเป็นจำนวนคู่สองเกาะ และเกาะที่มีสะพานเป็นจำนวนคี่สองเกาะ ถ้าเริ่มเดินจากเกาะใดเกาะหนึ่งที่มีสะพานเป็นจำนวนคี่ ก็จะข้ามทุกสะพานได้สะพานละครั้งเดียว ในรูปเริ่มที่เกาะ A และจบที่เกาะ D
เลออนฮาร์ด ออยเลอร์จึงแก้ปัญหาคณิตศาสตร์ที่มีชื่อเสียงได้อีกข้อหนึ่ง และยังวางรากฐานให้กับสิ่งที่ปัจจุบันเรียกว่าทฤษฎีกราฟ เพื่อเป็นเกียรติแก่เขา กราฟที่เดินผ่านทุกเส้นเชื่อมได้เส้นละครั้งเดียวจึงเรียกในทฤษฎีกราฟว่ากราฟออยเลอร์