इस खंड में हम ऑयलेरियन और हैमिल्टनियन ग्राफ देखेंगे। लेकिन इसमें गोता लगाने से पहले, पहले हमें यह देखना होगा कि ग्राफ़ में ट्रेल्स क्या हैं। मान लीजिए कि हमारे पास नीचे जैसा एक ग्राफ है -
पगडंडी एक पथ है, जो किनारों (v1, v2), (v2, v3), …, (vk - 1, vk) का एक क्रम है जिसमें सभी कोने (v1, v2, ..., vk) अलग नहीं हो सकते हैं , लेकिन सभी किनारे अलग हैं। इस उदाहरण में एक निशान है {(बी, ए), (ए, सी), (सी, डी), (डी, ए), (ए, एफ)} यह एक निशान है। लेकिन इसे उतना आसान रास्ता नहीं माना जाएगा जितना कि शीर्ष A को दो बार देखा जाता है। यदि पहला और अंतिम शीर्ष एक समान है, तो वह एक बंद पथ होगा।
यूलेरियन ट्रेल
ग्राफ G(V, E) में यूलेरियन ट्रेल एक निशान है, जिसमें प्रत्येक किनारे को ठीक एक बार शामिल किया जाता है। यदि G ने ऑयलरियन ट्रेल को बंद कर दिया है, तो उस ग्राफ को ऑयलेरियन ग्राफ कहा जाता है। दूसरे शब्दों में, हम कह सकते हैं कि एक ग्राफ G यूलेरियन ग्राफ होगा, यदि एक शीर्ष से शुरू होकर, हम प्रत्येक किनारे को ठीक एक बार पार कर सकते हैं और प्रारंभिक शीर्ष पर लौट सकते हैं। यूलर ने सिद्ध किया कि एक ग्राफ को यूलेरियन ग्राफ कहा जाता है यदि और केवल यदि इसके प्रत्येक शीर्ष की घात सम हो।
हैमिल्टनियन साइकिल
एक चक्र को हैमिल्टनियन चक्र कहा जाता है यदि यह ग्राफ G के प्रत्येक शीर्ष से होकर गुजरता है। ऐसे कई अलग-अलग प्रमेय हैं जो एक ग्राफ के लिए हैमिल्टनियन होने के लिए पर्याप्त शर्तें देते हैं। हालांकि, यह निर्धारित करने में समस्या है कि एक मनमाना ग्राफ हैमिल्टनियन है या नहीं, NPComplete समस्या है।