Tietze's graph
ग्राफ सिद्धांत के गणितीय क्षेत्र में, टिट्ज़ का ग्राफ 12 शीर्षों और 18 किनारों के साथ एक दिशाहीन घन ग्राफ है। इसका नाम हेनरिक फ्रांज फ्रेडरिक टिएट्ज़ के नाम पर रखा गया है, जिन्होंने 1910 में दिखाया था कि मोबियस पट्टी को छह क्षेत्रों में विभाजित किया जा सकता है जो सभी एक दूसरे को छूते हैं-तीन पट्टी की सीमा के साथ और तीन इसकी केंद्र रेखा के साथ-और इसलिए जो ग्राफ मोबियस पट्टी पर एम्बेड किए गए हैं, उन्हें छह रंगों की आवश्यकता हो सकती है। टिएत्ज़े के उपखंड के क्षेत्रों के सीमा खंड (मोबियस पट्टी की सीमा के साथ खंडों सहित) टिएत्ज़े के ग्राफ का एक एम्बेडिंग बनाते हैं। पीटरसन ग्राफ से संबंध टिटज़े के ग्राफ को पीटरसन ग्राफ से इसके एक शीर्ष को त्रिकोण से बदलकर बनाया जा सकता है। टिएट्ज़ ग्राफ की तरह, पीटरसन ग्राफ छह पारस्परिक रूप से स्पर्श करने वाले क्षेत्रों की सीमा बनाता है, लेकिन मोबियस पट्टी के बजाय प्रोजेक्टिव तल पर। यदि कोई प्रोजेक्टिव प्लेन के इस उपखंड से एक एकल शीर्ष के आसपास एक छेद को काटता है, तो चारों ओर के शीर्ष को छेद के चारों ओर क्षेत्र सीमाओं के एक त्रिकोण द्वारा प्रतिस्थापित किया जाता है, जो टिएट्ज़ ग्राफ का पहले वर्णित निर्माण देता है। हैमिल्टोनिसिटी टिएट्ज़ का ग्राफ और पीटरसन ग्राफ दोनों अधिकतम रूप से गैर-हैमिल्टोनियन हैंः उनका कोई हैमिल्टोनियन चक्र नहीं है, लेकिन किसी भी दो गैर-आसन्न शीर्षों को हैमिल्टोनियन पथ से जोड़ा जा सकता है। टिएट्ज़ का ग्राफ और पीटरसन ग्राफ 12 या उससे कम शीर्षों के साथ केवल 2-वर्टेक्स से जुड़े घन गैर-हैमिल्टनियन ग्राफ हैं। पीटरसन ग्राफ के विपरीत, टिट्ज़ का ग्राफ हाइपोहैमिल्टोनियन नहीं हैः इसके तीन त्रिभुज शीर्षों में से एक को हटाने से एक छोटा ग्राफ बनता है जो गैर-हैमिल्टोनियन रहता है। किनारे के रंग और सही मिलान किनारे के रंग के लिए टिट्ज़ के ग्राफ को चार रंगों की आवश्यकता होती है; यानी, इसका रंगीन सूचकांक 4 है। समान रूप से, टिट्ज़ के ग्राफ के किनारों को चार मिलानों में विभाजित किया जा सकता है, लेकिन कम नहीं। टिट्ज़ का ग्राफ एक स्नार्क की परिभाषा के हिस्से से मेल खाता हैः यह एक घन पुल रहित ग्राफ है जो 3-किनारे-रंगीन नहीं है। हालाँकि, अधिकांश लेखक बिना 3-चक्रों के रेखाचित्रों को सीमित करते हैं, इसलिए टिट्ज़ के रेखाचित्र को आम तौर पर एक रेखाचित्र नहीं माना जाता है। फिर भी, यह ग्राफ जे3 के लिए समरूप है, जो 1975 में आर. इसाक्स द्वारा पेश किए गए फूलों के एक अनंत परिवार का हिस्सा है। पीटरसन ग्राफ के विपरीत, टिएट्ज़ ग्राफ को चार पूर्ण मिलानों द्वारा कवर किया जा सकता है। यह गुण इस बात के प्रमाण में महत्वपूर्ण भूमिका निभाता है कि क्या एक ग्राफ को चार पूर्ण मिलानों द्वारा कवर किया जा सकता है, यह परीक्षण एन. पी.-पूर्ण है। अतिरिक्त गुण टिट्ज़ के ग्राफ में रंगीन संख्या 3, रंगीन सूचकांक 4, परिधि 3 और व्यास 3 है। स्वतंत्रता संख्या 5 है। इसके ऑटोमोर्फिज्म समूह का क्रम 12 है, और यह डायहेड्रल समूह D6 के समरूप है, जो एक षट्कोण की समरूपता का समूह है, जिसमें घूर्णन और प्रतिबिंब दोनों शामिल हैं। इस समूह में शीर्षों पर आकार 3 और आकार 6 की दो कक्षाएँ हैं, और इस प्रकार यह ग्राफ शीर्ष-सकर्मक नहीं है। गैलरी ड्यूरर ग्राफ और फ्रैंकलिन ग्राफ, दो अन्य 12-वर्टेक्स क्यूबिक ग्राफ नोट्स व्यक्तिगत ग्राफ नियमित ग्राफ भी देखें।