ในส่วนนี้ เราจะเห็นกราฟ Eulerian และ Hamiltonian แต่ก่อนที่จะดำดิ่งลงไปนั้น ก่อนอื่นเราต้องดูว่าเส้นกราฟคืออะไร สมมติว่าเรามีหนึ่งกราฟด้านล่าง −
เส้นทางคือเส้นทางซึ่งเป็นลำดับของขอบ (v1, v2), (v2, v3), …, (vk - 1, vk) ซึ่งจุดยอดทั้งหมด (v1, v2, … , vk) อาจไม่แตกต่างกัน แต่ขอบทั้งหมดมีความแตกต่างกัน ในตัวอย่างนี้ หนึ่งเทรลคือ {(B, A), (A, C), (C, D), (D, A), (A, F)} นี่คือเทรล แต่สิ่งนี้จะไม่ถือว่าเป็นเส้นทางธรรมดาเมื่อถึงจุดสุดยอด A สองครั้ง หากจุดยอดแรกและจุดสุดท้ายเท่ากัน จุดนั้นจะเป็นเส้นทางปิด
เส้นทางออยเลอร์
เส้นทาง Eulerian ในกราฟ G(V, E) เป็นเส้นทางที่รวมทุกขอบเพียงครั้งเดียว หาก G ได้ปิด Eulerian Trail กราฟนั้นจะเรียกว่ากราฟ Eulerian กล่าวอีกนัยหนึ่ง เราสามารถพูดได้ว่ากราฟ G จะเป็นกราฟ Eulerian หากเริ่มจากจุดยอดหนึ่งจุด เราสามารถข้ามทุกขอบเพียงครั้งเดียวและกลับสู่จุดยอดเริ่มต้น ออยเลอร์พิสูจน์ว่ากราฟเรียกว่ากราฟออยเลอเรียนก็ต่อเมื่อดีกรีของจุดยอดทุกอันเท่ากัน
วัฏจักรฮามิลโทเนียน
วัฏจักรหนึ่งเรียกว่าวัฏจักรแฮมิลตันถ้ามันผ่านทุกจุดยอดของกราฟ G มีทฤษฎีบทที่แตกต่างกันมากมายที่ให้เงื่อนไขที่เพียงพอสำหรับกราฟที่จะเป็นแฮมิลตัน อย่างไรก็ตาม ปัญหาในการพิจารณาว่ากราฟที่กำหนดเองคือ Hamiltonian หรือไม่ คือปัญหา NPComplete
