इस अनुभाग में हम यूलरियन और हैमिल्टनियन ग्राफ देखेंगे। लेकिन उसमें गोता लगाने से पहले, पहले हमें ग्राफ में ट्रेल्स (trails) क्या हैं, यह देखना होगा। मान लीजिए हमारे पास नीचे जैसा एक ग्राफ है:
ट्रेल एक पथ है, जो किनारों (v1, v2), (v2, v3), …, (vk-1, vk) का एक अनुक्रम है जिसमें सभी शीर्ष (v1, v2, …, vk) विशिष्ट नहीं हो सकते, लेकिन सभी किनारे विशिष्ट हैं। इस उदाहरण में एक ट्रेल है {(B, A), (A, C), (C, D), (D, A), (A, F)} यह एक ट्रेल है। लेकिन इसे सरल पथ (simple path) नहीं माना जाएगा क्योंकि शीर्ष A दो बार देखा गया है। यदि पहला और अंतिम शीर्ष समान हैं, तो वह एक बंद ट्रेल (closed trail) होगा।
यूलरियन ट्रेल (Eulerian Trail)
ग्राफ G(V, E) में एक यूलरियन ट्रेल एक ट्रेल है, जिसमें प्रत्येक किनारा ठीक एक बार शामिल होता है। यदि G में बंद यूलरियन ट्रेल है, तो उस ग्राफ को यूलरियन ग्राफ (Eulerian Graph) कहा जाता है। दूसरे शब्दों में, हम कह सकते हैं कि एक ग्राफ G यूलरियन ग्राफ होगा, यदि एक शीर्ष से शुरू करके, हम प्रत्येक किनारे को ठीक एक बार पार कर सकते हैं और प्रारंभिक शीर्ष पर वापस आ सकते हैं। यूलर ने साबित किया कि एक ग्राफ को यूलरियन ग्राफ कहा जाता है यदि और केवल यदि इसके प्रत्येक शीर्ष की डिग्री सम (even) है।
हैमिल्टनियन चक्र (Hamiltonian Cycle)
एक चक्र को हैमिल्टनियन चक्र कहा जाता है यदि यह ग्राफ G के प्रत्येक शीर्ष से होकर गुजरता है। कई अलग-अलग प्रमेय हैं जो ग्राफ के हैमिल्टनियन होने के लिए पर्याप्त शर्तें देते हैं। हालांकि, एक मनमाने ग्राफ के हैमिल्टनियन होने का निर्धारण करने की समस्या NP-Complete समस्या है।
