Wagner's theorem
ग्राफ सिद्धांत में, वैगनर की प्रमेय समतलीय ग्राफ का एक गणितीय निषिद्ध ग्राफ लक्षण वर्णन है, जिसका नाम क्लॉस वैगनर के नाम पर रखा गया है, जिसमें कहा गया है कि एक सीमित ग्राफ समतल है यदि और केवल तभी जब इसके लघु में न तो K5 (पांच शीर्षों पर पूर्ण ग्राफ) और न ही K3,3 (उपयोगिता ग्राफ, छह शीर्षों पर एक पूर्ण द्विदलीय ग्राफ) शामिल हो। यह ग्राफ माइनर के सिद्धांत में सबसे शुरुआती परिणामों में से एक था और इसे रॉबर्टसन-सीमोर प्रमेय के अग्रदूत के रूप में देखा जा सकता है। परिभाषाएँ और कथन किसी दिए गए ग्राफ का एक समतल एम्बेडिंग यूक्लिडियन तल में ग्राफ का एक चित्र है, जिसमें इसके शीर्षों के लिए बिंदु और इसके किनारों के लिए वक्र होते हैं, इस तरह से कि किनारों के जोड़े के बीच केवल प्रतिच्छेदन दोनों किनारों के एक सामान्य अंतिम बिंदु पर होते हैं। दिए गए ग्राफ का एक छोटा सा ग्राफ शीर्षों को हटाने, किनारों को हटाने और किनारों को सिकोड़ने से बना एक और ग्राफ है। जब एक किनारे को संकुचित किया जाता है, तो इसके दो अंतिम बिंदुओं को एक एकल शीर्ष बनाने के लिए मिला दिया जाता है। ग्राफ माइनर थ्योरी के कुछ संस्करणों में एक संकुचन के परिणामस्वरूप ग्राफ को सेल्फ-लूप और कई आसन्नताओं को हटाकर सरल बनाया जाता है, जबकि अन्य संस्करणों में मल्टीग्राफ की अनुमति है, लेकिन इस भिन्नता से वैगनर के प्रमेय पर कोई फर्क नहीं पड़ता है। वैगनर के प्रमेय में कहा गया है कि प्रत्येक ग्राफ में या तो एक समतलीय एम्बेडिंग होती है, या दो प्रकारों में से एक छोटा, पूर्ण ग्राफ K5 या पूर्ण द्विदलीय ग्राफ K3,3 होता है। (एक एकल ग्राफ के लिए दोनों प्रकार के लघु होना भी संभव है।) यदि दिया गया ग्राफ समतल है, तो इसके सभी छोटे भी हैंः शीर्ष और किनारे को हटाना स्पष्ट रूप से समतलता को बनाए रखता है, और संविदित किनारे के दो अंतिम बिंदुओं में से एक को जगह पर छोड़कर और संविदित किनारे के मार्ग के साथ दूसरे अंतिम बिंदु पर आने वाले सभी किनारों को रूट करके, किनारे का संकुचन भी समतलता-संरक्षण तरीके से किया जा सकता है। एक लघु-न्यूनतम गैर-समतल ग्राफ एक ऐसा ग्राफ है जो समतल नहीं है, लेकिन जिसमें सभी उचित लघु (कम से कम एक विलोपन या संकुचन से बने लघु) समतल हैं। वैगनर के प्रमेय को बताने का एक और तरीका यह है कि केवल दो लघु-न्यूनतम गैर-समतल ग्राफ, K5 और K3,3 हैं। एक अन्य परिणाम जिसे कभी-कभी वैगनर की प्रमेय के रूप में भी जाना जाता है, बताता है कि एक चार-जुड़ा ग्राफ समतल है यदि और केवल तभी जब इसमें कोई K5 लघु न हो। अर्थात्, संपर्क के एक उच्च स्तर को मानते हुए, ग्राफ K3,3 को लक्षण वर्णन में अनावश्यक बनाया जा सकता है, जिससे केवल एक निषिद्ध लघु, K5 रह जाता है। तदनुसार, केलमैन-सीमोर अनुमान में कहा गया है कि एक 5-जुड़ा ग्राफ समतल है यदि और केवल तभी जब इसमें टोपोलॉजिकल माइनर के रूप में K5 न हो। कुराटोव्स्की के प्रमेय के इतिहास और संबंध वैगनर ने 1937 में दोनों प्रमेयों को प्रकाशित किया, 1930 में कुराटोव्स्की के प्रमेय के प्रकाशन के बाद, जिसके अनुसार एक ग्राफ समतल है यदि और केवल तभी जब इसमें एक उपग्राफ के रूप में एक ही दो निषिद्ध ग्राफों K5 और K3,3 में से एक का उपखंड न हो। एक अर्थ में, कुराटोव्स्की की प्रमेय वैगनर की प्रमेय से अधिक मजबूत हैः उपखंड प्रक्रिया द्वारा बनाए गए प्रत्येक मार्ग में एक किनारे को छोड़कर सभी को संकुचित करके एक उपखंड को एक ही प्रकार के लघु में परिवर्तित किया जा सकता है, लेकिन एक लघु को एक ही प्रकार के उपखंड में परिवर्तित करना हमेशा संभव नहीं होता है। हालांकि, दो ग्राफ K5 और K3,3 के मामले में, यह साबित करना सीधा है कि एक ग्राफ जिसमें इन दो ग्राफों में से कम से कम एक लघु के रूप में है, उनमें से कम से कम एक उपखंड के रूप में भी है, इसलिए दोनों प्रमेय समतुल्य हैं। प्रभाव चार-जुड़े ग्राफों के लिए वैगनर के प्रमेय के मजबूत संस्करण का एक परिणाम उन ग्राफों को चिह्नित करना है जिनमें K5 माइनर नहीं है। प्रमेय को यह कहते हुए दोहराया जा सकता है कि ऐसा प्रत्येक ग्राफ या तो समतल है या इसे सरल टुकड़ों में विघटित किया जा सकता है। इस विचार का उपयोग करते हुए, के5-लघु-मुक्त ग्राफ को उन ग्राफों के रूप में चिह्नित किया जा सकता है जिन्हें समतलीय ग्राफ और आठ-वर्टेक्स वैगनर ग्राफ के संयोजन के रूप में बनाया जा सकता है, जो गुट-राशि संचालन द्वारा एक साथ चिपकाए जाते हैं। उदाहरण के लिए, K3,3 को इस तरह से तीन समतलीय ग्राफों के एक समूह-योग के रूप में बनाया जा सकता है, जिनमें से प्रत्येक टेट्राहेड्रल ग्राफ K4 की एक प्रति है। वैगनर का प्रमेय ग्राफ माइनर के सिद्धांत का एक महत्वपूर्ण अग्रदूत है, जो दो गहरे और दूरगामी परिणामों के प्रमाणों में समाप्त हुआः ग्राफ संरचना प्रमेय (वैगनर के K5-माइनर-मुक्त ग्राफ के गुट-योग अपघटन का एक सामान्यीकरण) और रॉबर्टसन-सीमोर प्रमेय (प्लेनर ग्राफ के निषिद्ध लघु लक्षण वर्णन का एक सामान्यीकरण, यह कहते हुए कि नाबालिगों को लेने के संचालन के तहत बंद किए गए प्रत्येक ग्राफ परिवार में निषिद्ध नाबालिगों की एक सीमित संख्या द्वारा लक्षण वर्णन होता है)। वैगनर के प्रमेय के अनुरूपों को मैट्रोइड्स के सिद्धांत तक भी बढ़ाया जा सकता हैः विशेष रूप से, वही दो ग्राफ K5 और K3,3 (तीन अन्य निषिद्ध विन्यासों के साथ) वर्जित मैट्रोइड नाबालिगों द्वारा ग्राफिक मैट्रोइड्स के लक्षण वर्णन में दिखाई देते हैं। प्लैनर ग्राफ ग्राफ लघु सिद्धांत ग्राफ सिद्धांत में प्रमेय