กราฟเบื้องต้น
กราฟ
การที่เริ่มต้นทฤษฎีว่าด้วยกราฟนี้ เกิดขึ้นในราวปี พ.ศ. 2279 คือ เมื่อออยเลอร์ นำปัญหาการเดินข้ามสะพานในเมืองเคอนิกสเบอร์ก ประเทศปรัสเซีย อันเป็นปัญหาเก่าแก่ที่ยังไม่เคยมีใครแก้ตกมาก่อนขึ้นมาพิจารณา ปัญหาดังกล่าวเป็นปัญหาเกี่ยวกับการเดินข้ามสะพานเจ็ดสะพาน ซึ่งเชื่อมโยงระหว่างฝั่งกับเกาะ และเกาะกับเกาะปัญหามีว่าเราจะเดินจากจุดใดจุดหนึ่งข้ามสะพานต่างๆ ให้ครบทุกสะพาน โดยเดินข้ามแต่ละสะพานเพียงครั้งเดียวแล้วกลับมาถึงจุดเดิมได้หรือไม่
ออยเลอร์แทนแผ่นดิน อันได้แก่ฝั่งแม่น้ำกับเกาะด้วยจุดสี่จุด และแทนสะพานทั้งเจ็ดด้วยเส้นเจ็ดเส้น เชื่อมโยงจุดทั้งสี่ตามที่มีสะพานเชื่อมโยงแผ่นดิน ซึ่งแทนด้วยจุดเหล่านั้น
รูปที่ได้นี้ก็คือกราฟแสดงการเชื่อมโยงแผ่นดินส่วนต่างๆ ด้วยสะพาน คงจะไม่ผิดหากเราจะกล่าวว่ากราฟรูปนี้ เป็นกราฟรูปแรกที่ถูกนำมาใช้ในการศึกษาทฤษฎีว่าด้วยกราฟ
ปัญหาเกี่ยวกับการเดินข้ามสะพานนั้น เมื่อแปลงมาเป็นภาษาของทฤษฎีว่าด้วยกราฟก็กลายเป็นปัญหาที่ว่า เราจะเริ่มต้นจากจุดใดจุดหนึ่ง ลากทับรอยเส้นต่างๆ ในกราฟรูปนี้ให้ครบทุกเส้น เส้นละครั้งเดียว แล้วในที่สุดลากมาบรรจบที่จุดตั้งต้นได้หรือไม่
ออยเลอร์มิได้จำกัดการแก้ปัญหาทำนองนี้ กับกราฟรูปนี้เพียงรูปเดียว เขาพิสูจน์ทฤษฎีบทซึ่งอาจนำไปใช้กับกราฟรูปใดๆ ก็ได้ การลองแก้ปัญหาในทำนองที่กล่าวไว้ข้างต้นกับรูปกราฟคงจะช่วยให้เราเข้าในทฤษฎีบทของออยเลอร์ได้ดีขึ้น