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