नेटवर्क की एक सीमा, अब हर आकार के लिए सिद्ध

कुछ बिंदु लीजिए और उनमें से कुछ जोड़ों को रेखाओं से जोड़ दीजिए। गणितज्ञ इसे ग्राफ़ कहते हैं: बिंदु इसके शीर्ष (vertices) हैं, रेखाएँ इसके कोर (edges), और दो शीर्षों के बीच की दूरी वह न्यूनतम कोर-संख्या है जो एक से दूसरे तक चलने के लिए चाहिए। अब दो नियम जोड़िए। हर शीर्ष-जोड़ा अधिकतम 2 की दूरी पर होना चाहिए — सीधे जुड़ा हुआ, या किसी साझा पड़ोसी के ज़रिए। और कोई कोर फ़ालतू नहीं हो सकता: किसी एक को भी हटाइए, तो कोई जोड़ा दो क़दमों से अधिक दूर हो जाता है। ऐसे ग्राफ़ को व्यास-2-क्रांतिक (diameter-2-critical) कहते हैं। इसमें कितने कोर हो सकते हैं?

मैंटल की छत, और एक साहसी अनुमान

1907 में Mantel ने सिद्ध किया कि n शीर्षों वाले ऐसे ग्राफ़ में, जिसमें कोई त्रिभुज न हो — यानी कोई तीन शीर्ष आपस में सब जुड़े न हों — अधिकतम ⌊n²/4⌋ कोर होते हैं: n का वर्ग चार से भाग, नीचे की ओर पूर्णांक तक पूर्णांकित। केवल एक ग्राफ़ उस छत तक पहुँचता है, संतुलित पूर्ण द्विभाजी ग्राफ़ (balanced complete bipartite graph): आकार में जितने संभव हो उतने बराबर दो समूह, एक का हर शीर्ष दूसरे के हर शीर्ष से जुड़ा, किसी समूह के भीतर कोई कोर नहीं।

हर त्रिभुज-रहित ग्राफ़, जिसमें त्रिभुज बनाए बिना एक भी और कोर नहीं जोड़ा जा सकता, व्यास-2-क्रांतिक होता है। उलटा सच नहीं है: कुछ व्यास-2-क्रांतिक ग्राफ़ों में त्रिभुज होते हैं।

7 शीर्षों और 9 कोरों वाला एक व्यास-2-क्रांतिक ग्राफ़, जिसमें त्रिभुज v1v3v5 है। v1v3 को हटाने से v2 और v3 के बीच का इकलौता दो-क़दमी रास्ता नष्ट हो जाता है; त्रिभुज के बाहर का कोई कोर हटाने से उसके सिरों के बीच कोई दो-क़दमी रास्ता नहीं बचता। — चित्र 1, Das & Fox (2026), arXiv:2610.39032.

अनुमान यह था कि त्रिभुजों से कुछ हासिल नहीं होता: n शीर्षों वाले व्यास-2-क्रांतिक ग्राफ़ में भी अधिकतम ⌊n²/4⌋ कोर होते हैं, और संतुलित पूर्ण द्विभाजी ग्राफ़ ही अकेला इस तक पहुँचता है। मैंटल का प्रमेय इसकी एक विशेष स्थिति के रूप में निकल आता। चित्र के 7 शीर्षों के लिए छत 12 कोर है।

2 की एक मीनार

Zoltán Füredi के बताए अनुसार, Erdős के मुताबिक़ यह प्रश्न 1960 के दशक में Ore के काम तक जाता है। Ján Plesník ने 1975 में कोर-सीमा को एक अनुमान के रूप में रखा; Murty और Simon ने इसे स्वतंत्र रूप से प्रस्तावित किया और जोड़ा कि संतुलित पूर्ण द्विभाजी ग्राफ़ ही एकमात्र चरम स्थिति है — इसीलिए मूर्ति–साइमन अनुमान (Murty–Simon conjecture)। 1970 और 1980 के दशकों में c·n² रूप की सीमाएँ धीरे-धीरे नीचे आती गईं, c लगातार 1/4 के क़रीब होता गया।

1992 में Füredi ने नियमितता विधियों (regularity methods) — Szemerédi की नियमितता प्रमेयिका से निकले औज़ारों — से हर पर्याप्त बड़े n के लिए अनुमान सिद्ध किया। क़ीमत थी शुरुआती आकार: n को कम से कम 2 की लगभग 10¹⁴ ऊँची मीनार होना था, यानी 2 की घात 2 की घात 2…, जिसे ऊपर से नीचे की ओर हल किया जाता है — हर 2 को अपने ऊपर की हर चीज़ की घात तक उठाया जाता है — ढेर में लगभग 10¹⁴ दो के साथ। उस आकार से नीचे केवल ग्राफ़ों के कुछ विशेष परिवार ही सुलझाए गए थे।

कोर बनाम अनुपस्थित कोर

स्टैनफ़र्ड विश्वविद्यालय के गणित विभाग के Sanjana Das और Jacob Fox का नया प्रमाण 3 और उससे ऊपर हर n के लिए काम करता है। यह एक अधिकतमल मिलान (maximal matching) का उपयोग करता है: कोरों का एक समुच्चय, जिनमें कोई दो एक शीर्ष साझा नहीं करते, और जिसमें कोई और कोर जोड़ा नहीं जा सकता बिना दो कोरों के मिल जाने के। n शीर्षों पर एक मिलान में अधिकतम ⌊n/2⌋ कोर होते हैं।

मुख्य प्रमेयिका: व्यास-2-क्रांतिक ग्राफ़ में, किसी भी अधिकतमल मिलान के लिए, मिलान से बाहर के कोर कभी भी अ-कोरों से अधिक नहीं होते — अ-कोर यानी शीर्षों के वे जोड़े जो जुड़े नहीं हैं। बाक़ी अंकगणित है। कोरों की संख्या का दोगुना अधिकतम जोड़ों की संख्या और मिलान के आकार के योग जितना है। 10 शीर्षों के साथ: 45 जोड़े और अधिकतम 5 मिलान-कोर मिलकर 50 होते हैं, इसलिए अधिकतम 25 कोर। हर n के लिए यह योग ठीक मैंटल की छत का दोगुना निकलता है।

प्रमेयिका स्वयं एक बारीक हिसाब-किताब है। कोई अ-कोर क्रांतिक है अगर उसके सिरों को केवल एक दो-क़दमी रास्ता जोड़ता हो, जैसा चित्र 1 के सभी बारह अ-कोरों के साथ है। लेखक हर क्रांतिक अ-कोर को उसके रास्ते के दो कोरों से जोड़ते हैं और इससे बने जाल को जुड़े हुए टुकड़ों में बाँटते हैं। एक टुकड़े में क्रांतिक अ-कोरों से अधिकतम एक कोर ज़्यादा होता है, और उस अधिशेष वाले हर टुकड़े की क़ीमत किसी अ-क्रांतिक अ-कोर से चुकानी होती है। उन्हें ढूँढ़ने के लिए लेखक स्विच निकास (switch exits) का उपयोग करते हैं: टुकड़े का कोई कोर या क्रांतिक अ-कोर लीजिए और उसके एक सिरे को मिलान में उस सिरे के साथी से बदल दीजिए। हर अ-क्रांतिक अ-कोर पर अधिकतम दो बार दावा होता है, अधिशेष वाला हर टुकड़ा कम से कम दो दावे करता है, और गिनती पूरी हो जाती है।

किसने क्या खोजा

“यह प्रमाण अधिकांशतः AI ने खोजा, विशेष रूप से GPT-5.6 Sol ने, 11 अगस्त 2026 को,” लेखक एक संक्षिप्त AI वक्तव्य में लिखते हैं। मॉडल ने ⌊n²/4⌋ सीमा का एक पूरा प्रमाण खोजा, जिसे उन्होंने सरल बनाया। शीर्षों की सम संख्या के लिए उसने यह भी सिद्ध किया कि संतुलित पूर्ण द्विभाजी ग्राफ़ ही एकमात्र चरम स्थिति है, Sumner द्वारा सिद्ध एक तथ्य के सहारे, जो उन ग्राफ़ों के बारे में है जिनमें हर अधिकतमल मिलान पूर्ण (perfect) होता है, यानी हर शीर्ष को ढकता है।

शीर्षों की विषम संख्या के साथ कोई मिलान पूर्ण नहीं होता, और कई ग्राफ़ों में हर अधिकतमल मिलान ठीक एक शीर्ष छोड़ देता है: मॉडल के तर्क को इसके अनुरूप नहीं ढाला जा सका। लेखकों ने समानता वाली स्थिति का एक अलग प्रमाण खोजा, जो हर n के लिए मान्य है, और शोधपत्र ख़ुद लिखा; GPT-6 Astra से एक अंतिम बार गुज़ारने पर “कुछ छोटे संपादन” हुए। यह शोधपत्र एक प्रीप्रिंट है, अभी सहकर्मी-समीक्षित नहीं, और इसमें तर्क के किसी कंप्यूटर-जाँचे संस्करण का ज़िक्र नहीं है।

वापस 1907 की ओर

अगर कोई ग्राफ़ छत को छू ले, तो मुख्य असमिका हर अधिकतमल मिलान के लिए समिका बन जाती है। मिलानों को चतुराई से चुनकर लेखक दिखाते हैं कि ऐसा ग्राफ़ या तो एक तारा (star) है — एक शीर्ष बाक़ी सबसे जुड़ा, और कुछ नहीं — या उसमें कोई क्रांतिक अ-कोर है ही नहीं। व्यास-2-क्रांतिक ग्राफ़ में त्रिभुज का हर कोर किसी क्रांतिक रास्ते पर होता है, इसलिए क्रांतिक अ-कोर न होने का अर्थ है त्रिभुज न होना; तारे में भी कोई त्रिभुज नहीं होता। इसलिए छत को छूने वाला ग्राफ़ त्रिभुज-रहित है, और अंतिम क़दम वही प्रमेय है जिसे यह अनुमान मज़बूत करने निकला था: Mantel का 1907 का परिणाम, जो संतुलित पूर्ण द्विभाजी ग्राफ़ को छत पर अकेला छोड़ देता है।