Moser spindle
ग्राफ सिद्धांत में, गणित की एक शाखा, मोजर स्पिंडल (जिसे मोजर्स स्पिंडल या मोजर ग्राफ भी कहा जाता है) एक दिशाहीन ग्राफ है, जिसका नाम सात शीर्षों और ग्यारह किनारों के साथ गणितविदों लियो मोजर और उनके भाई विलियम के नाम पर रखा गया है। यह एक इकाई दूरी ग्राफ है जिसमें किसी भी ग्राफ रंग में चार रंगों की आवश्यकता होती है, और इसके अस्तित्व का उपयोग यह साबित करने के लिए किया जा सकता है कि तल की रंगीन संख्या कम से कम चार है। मोजर स्पिंडल को ग्योरगी हाजोस के बाद हाजोस ग्राफ भी कहा गया है, क्योंकि इसे हाजोस निर्माण के एक उदाहरण के रूप में देखा जा सकता है। हालांकि, "हाजोस ग्राफ" नाम को एक भिन्न ग्राफ पर भी लागू किया गया है, जो एक षट्कोण के भीतर उत्कीर्ण त्रिभुज के रूप में है। एक इकाई दूरी ग्राफ के रूप में, मोजर स्पिंडल 60 और 120 डिग्री कोणों के साथ दो समभुज द्वारा बनाया जाता है, ताकि समभुज के पक्ष और छोटे विकर्ण समबाहु त्रिभुज बनाते हैं। दो रोंबी को समतल में रखा गया है, जो अपने एक तीव्र-कोण वाले शीर्ष को इस तरह से साझा करते हैं कि शेष दो तीव्र-कोण वाले शीर्ष एक दूसरे से एक इकाई दूरी पर हैं। ग्राफ के ग्यारह किनारे आठ समभुज पक्ष, समभुज के दो छोटे विकर्ण और तीव्र-कोण वाले शीर्षों की इकाई-दूरी जोड़ी के बीच का किनारा हैं। मोजर स्पिंडल को चार शीर्षों पर दो पूर्ण ग्राफों के साथ शुरू होने वाले हाजोस निर्माण का उपयोग करते हुए, ज्यामितीय एम्बेडिंग के संदर्भ के बिना, ग्राफ-सैद्धांतिक रूप से भी बनाया जा सकता है। यह निर्माण प्रत्येक पूर्ण ग्राफ से एक किनारे को हटा देता है, हटाए गए किनारों के दो अंतिम बिंदुओं को दोनों गुटों द्वारा साझा किए गए एक शीर्ष में मिला देता है, और हटाए गए किनारे के शेष दो अंतिम बिंदुओं को जोड़ने के लिए एक नया किनारा जोड़ता है। मोजर स्पिंडल के निर्माण का एक अन्य तरीका उपयोगिता ग्राफ K3,3 से इसके एक किनारे को उपविभाजित करके बनाए गए ग्राफ के पूरक ग्राफ के रूप में है। हैडविगर-नेल्सन समस्या के लिए अनुप्रयोग हैडविगर-नेल्सन समस्या यह पूछती है कि यूक्लिडियन तल के बिंदुओं को इस तरह से रंगने के लिए कितने रंगों की आवश्यकता होती है कि एक दूसरे से इकाई दूरी पर बिंदुओं की प्रत्येक जोड़ी को अलग-अलग रंग दिए जाते हैं। अर्थात्, यह अनंत ग्राफ की वर्णात्मक संख्या के लिए पूछता है जिसके शीर्ष समतल में सभी बिंदु हैं और जिनके किनारे इकाई दूरी पर बिंदुओं के सभी जोड़े हैं। मोजर स्पिंडल को किसी भी ग्राफ रंग में चार रंगों की आवश्यकता होती हैः दो रोंबी में से किसी एक के तीन रंगों में, जिससे यह बनता है, रोंबी के दो तीव्र-कोण वाले शीर्षों का रंग अनिवार्य रूप से एक दूसरे के समान होगा। लेकिन अगर दो समभुज के साझा शीर्ष का रंग दो विपरीत तीव्र-कोण वाले शीर्षों के समान है, तो इन दोनों शीर्षों का रंग एक-दूसरे के समान है, इस आवश्यकता का उल्लंघन करते हुए कि उन्हें जोड़ने वाले किनारे में अलग-अलग रंग के अंतिम बिंदु हैं। इस विरोधाभास से पता चलता है कि तीन रंग असंभव हैं, इसलिए कम से कम चार रंग आवश्यक हैं। मोजर स्पिंडल को रंग देने के लिए चार रंग भी पर्याप्त हैं, एक तथ्य जो उदाहरण के लिए इस तथ्य से मिलता है कि इसकी अधोगति तीन है। एक वैकल्पिक प्रमाण कि मोजर स्पिंडल को चार रंगों की आवश्यकता होती है, हाजोस निर्माण से मिलता है। जिन दोनों पूर्ण ग्राफों से मोजर स्पिंडल बनता है, उन्हें चार रंगों की आवश्यकता होती है, और हाजोस निर्माण इस गुण को संरक्षित करता है। इससे भी अधिक सीधे, मोजर स्पिंडल में प्रत्येक स्वतंत्र सेट में अधिक से अधिक दो शीर्ष होते हैं, इसलिए सभी सात शीर्षों को कवर करने के लिए कम से कम चार स्वतंत्र सेट लगते हैं। चूँकि मोजर स्पिंडल तल के अनंत इकाई दूरी ग्राफ का एक उपग्राफ है, इसलिए तल के ग्राफ को भी किसी भी रंग में कम से कम चार रंगों की आवश्यकता होती है। डी ब्रुइजन-एर्डोस प्रमेय द्वारा (इस धारणा के साथ कि पसंद का स्वयंसिद्ध सत्य है), तल की वर्णात्मक संख्या इसके किसी भी परिमित उपग्राफ की सबसे बड़ी वर्णात्मक संख्या के समान है; 2018 में 5-वर्णात्मक इकाई दूरी ग्राफ के एक परिवार की खोज होने तक, अनंत इकाई दूरी ग्राफ का कोई उपग्राफ नहीं पाया गया था जिसके लिए मोजर स्पिंडल की तुलना में बड़ी संख्या में रंगों की आवश्यकता होती है। हालांकि, तल की रंगीन संख्या के लिए सबसे अच्छी ऊपरी सीमा सात है, जो मोजर स्पिंडल के लिए आवश्यक रंगों की संख्या से काफी अधिक है। अन्य गुण और अनुप्रयोग मोजर स्पिंडल एक समतलीय ग्राफ है, जिसका अर्थ है कि इसे समतल में पार किए बिना खींचा जा सकता है। हालांकि, सीधी रेखा के किनारों के साथ ऐसा रेखाचित्र बनाना संभव नहीं है जो एक इकाई दूरी का रेखाचित्र भी हो; यानी, यह एक माचिस का रेखाचित्र नहीं है। मोजर स्पिंडल भी एक लमन ग्राफ है, जिसका अर्थ है कि यह तल में एम्बेड होने पर एक न्यूनतम कठोर प्रणाली बनाता है। एक समतलीय लमन ग्राफ के रूप में, यह एक नुकीले छद्म त्रिभुज का ग्राफ है, जिसका अर्थ है कि इसे तल में इस तरह से एम्बेड किया जा सकता है कि असीमित चेहरा एम्बेडिंग का उत्तल पतवार हो और प्रत्येक बंधा हुआ चेहरा केवल तीन उत्तल शीर्षों के साथ एक छद्म त्रिभुज हो। मोजर ग्राफ का पूरक ग्राफ एक त्रिभुज-मुक्त ग्राफ है। इस प्रकार, मोजर ग्राफ की इकाई दूरी एम्बेडिंग का उपयोग समतल में सात बिंदुओं को रखने की समस्या को इस तरह से हल करने के लिए किया जा सकता है कि प्रत्येक तीन अंकों में एक दूसरे से इकाई दूरी पर कम से कम एक जोड़ा हो। मोजर स्पिंडल में किसी भी किनारे को जोड़ने से एक ग्राफ में परिणाम मिलता है जिसे एक इकाई दूरी ग्राफ के रूप में तल में एम्बेड नहीं किया जा सकता है, और मोजर स्पिंडल से किसी भी छोटे इकाई दूरी ग्राफ के लिए एक ग्राफ समरूपता मौजूद नहीं है। मोजर स्पिंडल के इन दो गुणों का उपयोग परीक्षण की एन. पी.-कठोरता को दिखाने के लिए किया गया था कि क्या दिए गए ग्राफ में द्वि-आयामी इकाई दूरी का प्रतिनिधित्व है; प्रमाण 3सैट से कमी का उपयोग करता है जिसमें मोजर स्पिंडल का उपयोग कमी में केंद्रीय सत्य-सेटिंग उपकरण के रूप में किया जाता है। मोजर स्पिंडल का उपयोग यूक्लिडियन रैमसे सिद्धांत में एक परिणाम साबित करने के लिए भी किया जा सकता हैः यदि T समतल में कोई त्रिभुज है, और तल के बिंदु दो रंग के काले और सफेद हैं, तो या तो T का एक काला अनुवाद होता है या एक दूसरे से इकाई दूरी पर सफेद बिंदुओं की एक जोड़ी होती है। यदि एम + टी में कोई सफेद इकाई-दूरी जोड़ी नहीं है, तो एम + टी में मोजर स्पिंडल की तीन प्रतियों में से प्रत्येक में अधिक से अधिक दो सफेद बिंदु होने चाहिए, क्योंकि प्रत्येक प्रति में सफेद बिंदुओं को एक स्वतंत्र सेट बनाना चाहिए और मोजर स्पिंडल में सबसे बड़े स्वतंत्र सेट का आकार दो होना चाहिए। इसलिए, मोजर स्पिंडल के सात शीर्षों में से, अधिक से अधिक छह हैं जिनकी एम + टी में एक सफेद प्रति है, इसलिए सात शीर्षों में से एक होना चाहिए जिनकी सभी प्रतियां काली हैं। लेकिन फिर इस शीर्ष की तीन प्रतियां टी का अनुवाद बनाती हैं। गोलम्ब ग्राफ संदर्भ भी देखें बाहरी लिंक व्यक्तिगत ग्राफ समतल ग्राफ