चार-रंग प्रमेय और कम्प्यूटेशनल गणित की क्रांति: 100 साल की पहेली और मशीन द्वारा प्रमाण का दर्शन

गणित के इतिहास में, सबसे प्रसिद्ध और साथ ही सबसे विवादास्पद प्रमेयों में से एक ‘चार-रंग प्रमेय (Four Color Theorem)’ है। ‘किसी भी समतल मानचित्र को, जिसमें आसन्न क्षेत्र अलग-अलग रंगों में रंगे हों, रंगने के लिए 4 रंग पर्याप्त हैं’, यह एक ऐसा दावा है जिसे एक प्राथमिक स्कूल का छात्र भी समझ सकता है, लेकिन इसके प्रमाण के लिए एक सदी से अधिक का समय और ‘कंप्यूटर द्वारा प्रमाण’ जैसे प्रतिमान बदलाव (paradigm shift) की आवश्यकता थी, जिसने गणित के अध्ययन की नींव को हिलाकर रख दिया।

इस लेख में, हम 1852 के एक साधारण प्रश्न से शुरू करते हुए, प्रतिभाशाली लोगों की चुनौतियों और असफलताओं से लेकर आधुनिक गणित के उस मुकाम तक चार-रंग प्रमेय की पूरी तस्वीर को गणितीय, ऐतिहासिक और दार्शनिक दृष्टिकोण से गहराई से स्पष्ट करेंगे, जहाँ कंप्यूटर जैसी नई बुद्धि को सहयोगी बनाया गया। विशेष रूप से, हम केम्पे के झूठे प्रमाण और हीवुड के प्रति-उदाहरण की ज्यामितीय संरचना, पांच-रंग प्रमेय का पूर्ण प्रमाण, डिस्चार्जिंग विधि (Discharging method) के गणित, अपेल और हाकेन के एल्गोरिदम, Coq द्वारा औपचारिक प्रमाण (formal proof) के विवरण और NP-पूर्णता के साथ इसके संबंध जैसे गहन गणितीय विषयों पर विस्तार से चर्चा करेंगे।

अध्याय 1: 1852, फ्रांसिस गुथरी का साधारण प्रश्न और ग्राफ सिद्धांत में इसका उत्थान

मानचित्र रंगने की समस्या का प्रस्ताव

कहानी की शुरुआत 1852 में होती है, जब फ्रांसिस गुथरी नामक एक युवक, जिसने हाल ही में यूनिवर्सिटी कॉलेज लंदन से स्नातक किया था, इंग्लैंड के काउंटियों के एक मानचित्र को रंग रहा था। उसे एक अजीब तथ्य का एहसास हुआ: ‘चाहे मानचित्र कितना भी जटिल क्यों न हो, आसन्न काउंटियों को अलग-अलग रंगों में रंगने के लिए क्या 4 रंग पर्याप्त नहीं होंगे?’

फ्रांसिस ने इस प्रश्न को अपने छोटे भाई फ्रेडरिक गुथरी के साथ साझा किया, जो उस समय यूनिवर्सिटी कॉलेज में गणित पढ़ रहे थे। फ्रेडरिक ने इस समस्या को अपने सलाहकार और उस समय के प्रमुख गणितज्ञों में से एक, ऑगस्टस डी मॉर्गन के सामने प्रस्तुत किया। डी मॉर्गन तुरंत इस समस्या की रोचकता से आकर्षित हो गए और उन्होंने अपने मित्र विलियम रोवन हैमिल्टन और अन्य लोगों के साथ एक पत्र के माध्यम से इसे साझा किया। यह वह क्षण था जब गणित के इतिहास में शानदार ढंग से चमकने वाली ‘चार-रंग की समस्या’ का जन्म हुआ।

यूलर का बहुफलक प्रमेय और समतल ग्राफ की द्वैतता (Duality)

मानचित्र रंगने की समस्या को गणितीय रूप से कठोरता से संभालने के लिए, इसे ग्राफ सिद्धांत में सूत्रबद्ध करना आवश्यक है। यदि हम मानचित्र पर प्रत्येक क्षेत्र (देश या राज्य) को ‘शीर्ष (Vertex)’ के रूप में लेते हैं और आसन्न क्षेत्रों को ‘किनारे (Edge)’ से जोड़ते हैं, तो हमें एक ‘समतल ग्राफ (Planar Graph)’ प्राप्त होता है जहाँ समतल पर किनारे एक-दूसरे को पार नहीं करते हैं। इस परिवर्तन को ‘द्वैत ग्राफ (Dual Graph)’ लेने की प्रक्रिया के रूप में जाना जाता है। मूल मानचित्र की सीमाएँ ग्राफ के किनारों से, और सतहें शीर्षों से मेल खाती हैं।

चार-रंग की समस्या ग्राफ की ‘शीर्ष रंगने की समस्या (Vertex Coloring Problem)’ में बदल जाती है: ‘क्या किसी समतल ग्राफ के शीर्षों को 4 रंगों से इस प्रकार रंगा जा सकता है कि आसन्न शीर्षों का रंग अलग-अलग हो?’

यहाँ एक अत्यंत महत्वपूर्ण भूमिका लियोनहार्ड यूलर द्वारा खोजे गए बहुफलक प्रमेय (Polyhedron formula) द्वारा निभाई जाती है। एक जुड़े हुए समतल ग्राफ में, यदि शीर्षों की संख्या $V$, किनारों की संख्या $E$ और फलकों (Faces) की संख्या $F$ है, तो निम्नलिखित अपरिवर्तनीय संबंध लागू होता है।

$$V - E + F = 2$$

इस प्रमेय और समतल ग्राफ के मूल गुणों को जोड़कर, समतल ग्राफ की संरचना पर शक्तिशाली प्रतिबंध (constraints) प्राप्त किए जा सकते हैं। मान लें कि ग्राफ एक साधारण ग्राफ है जिसमें कई किनारे (multiple edges) या स्वयं-लूप (self-loops) नहीं हैं, और आगे एक ‘अधिकतम समतल ग्राफ (Maximal Planar Graph)’ पर विचार करें जहाँ सभी फलक त्रिकोण हैं। चूंकि किनारे जोड़ने से किसी भी समतल ग्राफ को अधिकतम समतल ग्राफ बनाने पर आवश्यक रंगों की संख्या नहीं बढ़ती है, इसलिए केवल अधिकतम समतल ग्राफ के लिए चार-रंग प्रमेय सिद्ध करना पर्याप्त है।

अधिकतम समतल ग्राफ में, प्रत्येक फलक ठीक 3 किनारों से घिरा होता है। चूंकि एक किनारा ठीक 2 फलकों की सीमा बनाता है, इसलिए फलकों की संख्या और किनारों की संख्या के बीच निम्नलिखित संबंध सख्ती से स्थापित होता है।

$$3F = 2E$$

इसे यूलर के सूत्र में प्रतिस्थापित (substitute) करके $F$ को खत्म करते हैं। $F = \frac{2}{3}E$ को $V - E + F = 2$ में प्रतिस्थापित करने पर,

$$V - E + \frac{2}{3}E = 2 \implies V - \frac{1}{3}E = 2 \implies 3V - E = 6 \implies E = 3V - 6$$

सामान्य साधारण समतल ग्राफ में, चूंकि फलक 3 या अधिक किनारों से घिरे होते हैं, $3F \leq 2E$, और निम्नलिखित असमानता (inequality) प्राप्त होती है।

$$E \leq 3V - 6$$

यह असमानता दर्शाती है कि समतल ग्राफ में किनारों के घनत्व (density) की एक सख्त ऊपरी सीमा होती है। यहाँ से, आइए प्रत्येक शीर्ष की डिग्री (Degree, $\deg(v)$) पर विचार करें। ग्राफ के सभी शीर्षों की डिग्री का योग किनारों की संख्या का ठीक दोगुना होता है (हैंडशेकिंग लेम्मा)।

$$\sum_{v \in V} \deg(v) = 2E$$

पिछली असमानता $2E \leq 6V - 12$ का उपयोग करने पर,

$$\sum_{v \in V} \deg(v) \leq 6V - 12$$

दोनों पक्षों को शीर्षों की संख्या $V$ से विभाजित करने पर, शीर्षों की औसत डिग्री प्राप्त होती है।

$$\frac{1}{V} \sum_{v \in V} \deg(v) \leq 6 - \frac{12}{V} < 6$$

औसत डिग्री का सख्ती से 6 से कम होने का अर्थ है कि गणितीय रूप से यह पूरी तरह से सिद्ध हो गया है कि ‘कम से कम एक शीर्ष ऐसा होना चाहिए जिसकी डिग्री 5 या उससे कम हो’। अर्थात्, किसी भी साधारण समतल ग्राफ में कम से कम एक शीर्ष मौजूद होता है जिसकी डिग्री 1, 2, 3, 4, या 5 में से कोई एक होती है। यह तथ्य ‘अपरिहार्य विन्यास (Unavoidable Configuration)’ की अवधारणा का सबसे बुनियादी प्रस्थान बिंदु है, जिसकी चर्चा बाद में की गई है, और चार-रंग प्रमेय के प्रमाण का परम आधार है।

अध्याय 2: अल्फ्रेड केम्पे का “प्रमाण” और 11 साल बाद इसका पतन

केम्पे श्रृंखला (Kempe Chain) की अवधारणा और शानदार “प्रमाण”

1879 में, अल्फ्रेड ब्रेड केम्पे (Alfred Kempe), जो एक ब्रिटिश वकील और गणितज्ञ थे, ने अंततः ‘Nature’ और ‘American Journal of Mathematics’ पत्रिकाओं में चार-रंग की समस्या का ‘प्रमाण’ प्रकाशित किया। उनका प्रमाण अत्यंत मौलिक था और अगले 11 वर्षों तक दुनिया भर के गणितीय समुदाय द्वारा इसे सही माना गया।

केम्पे के प्रमाण का मूल एक अभूतपूर्व विचार था जिसे अब ‘केम्पे श्रृंखला (Kempe Chain)’ कहा जाता है। उन्होंने गणितीय आगमन (Mathematical Induction) का उपयोग किया। उन्होंने माना कि चार-रंग प्रमेय $k$ शीर्षों वाले सभी समतल ग्राफ़ के लिए सत्य है, और यह दिखाने का प्रयास किया कि यह $k+1$ शीर्षों वाले ग्राफ़ के लिए भी सत्य है।

पूर्वोक्त यूलर के प्रमेय से, $k+1$ शीर्षों वाले समतल ग्राफ $G$ में हमेशा 5 या उससे कम डिग्री वाला एक शीर्ष $v$ मौजूद होता है। ग्राफ $G$ पर विचार करें जिससे शीर्ष $v$ और उससे जुड़े किनारों को हटाकर ग्राफ $G'$ प्राप्त किया गया है। चूंकि $G'$ में शीर्षों की संख्या $k$ है, इसलिए आगमन परिकल्पना (induction hypothesis) द्वारा इसे 4 रंगों (यहाँ हम मान लेते हैं कि लाल, नीला, हरा, पीला) से रंगा जा सकता है। इसके बाद, हम $v$ को वापस लाते हैं और रंगने का प्रयास करते हैं।

यदि $v$ की डिग्री 3 या उससे कम है: $v$ के आसन्न शीर्ष अधिकतम 3 हैं। इसलिए, 4 रंगों में से कम से कम 1 रंग का उपयोग आसन्न शीर्षों पर नहीं किया गया है। उस अप्रयुक्त रंग को $v$ पर रंगने से प्रमाण पूरा हो जाता है।
यदि $v$ की डिग्री 4 है: मान लें कि $v$ के 4 आसन्न शीर्षों (जिन्हें दक्षिणावर्त $v_1, v_2, v_3, v_4$ कहते हैं) को सभी अलग-अलग रंगों (लाल, नीला, हरा, पीला) से रंगा गया है। यहाँ, पूरे ग्राफ से केवल ‘लाल’ और ‘हरे’ रंग से रंगे शीर्षों और उन्हें जोड़ने वाले किनारों से निकाले गए उप-ग्राफ पर विचार करें। यदि $v_1$ (लाल) और $v_3$ (हरा) इस लाल-हरे उप-ग्राफ के भीतर जुड़े हुए नहीं हैं (अर्थात्, लाल और हरे शीर्षों का अनुसरण करते हुए $v_1$ से $v_3$ तक जाने वाला कोई मार्ग नहीं है), तो हम $v_1$ वाले जुड़े घटक (connected component) के रंगों को उलट सकते हैं (लाल को हरे में, हरे को लाल में)। इसे ‘केम्पे श्रृंखला उलटना (Kempe chain inversion)’ कहा जाता है। उलटने के बाद, $v_1$ हरा हो जाता है, और आस-पास के रंग नीले, हरे, हरे, और पीले रंग (3 रंग) में घट जाते हैं। इससे $v$ को लाल रंग से रंगना संभव हो जाता है। यदि $v_1$ और $v_3$ जुड़े हुए हैं, तो समतल ग्राफ के टोपोलॉजिकल गुणों (जॉर्डन कर्व थ्योरम) के कारण, $v_1$ और $v_3$ को जोड़ने वाला लाल-हरा मार्ग $v_2$ (नीला) और $v_4$ (पीला) को अलग कर देता है। इसलिए, $v_2$ और $v_4$ किसी भी नीले-पीले केम्पे श्रृंखला से कभी नहीं जुड़ सकते हैं, और $v_2$ वाले नीले-पीले घटक को उलटा जा सकता है। किसी भी मामले में, $v$ के आस-पास के रंगों की संख्या को 3 तक कम किया जा सकता है, और $v$ को रंगा जा सकता है।
यदि $v$ की डिग्री 5 है: मान लें कि $v$ के 5 आसन्न शीर्ष $v_1, v_2, v_3, v_4, v_5$ क्रमशः लाल, नीले, हरे, पीले, और लाल (चूंकि 5 हैं, 1 रंग दोहराया जाएगा) से रंगे गए हैं। केम्पे ने दावा किया कि डिग्री 4 के मामले के तर्क का विस्तार करके और 2 अलग-अलग केम्पे श्रृंखलाओं (उदाहरण के लिए, लाल-हरी श्रृंखला और लाल-पीली श्रृंखला) के उलटाव (inversion) को चतुराई से जोड़कर, $v$ के आस-पास के रंगों की संख्या को हमेशा 3 या उससे कम किया जा सकता है। उनका तरीका एक दोहरे तर्क को लागू करना था कि यदि एक जुड़ा हुआ है तो दूसरा अलग हो जाएगा।

यह प्रमाण सहज और सुंदर था, और तर्क में कोई खामी नजर नहीं आती थी। उस समय के गणितज्ञों को इसमें कोई संदेह नहीं था कि चार-रंग की समस्या पूरी तरह से हल हो गई है।

हीवुड का प्रति-उदाहरण ग्राफ: “दोहरे केम्पे श्रृंखलाओं के प्रतिच्छेदन” की घातक खामी

हालाँकि, 1890 में, पर्सी जॉन हीवुड (Percy John Heawood) नामक 29 वर्षीय गणितज्ञ ने केम्पे के शोधपत्र को ध्यान से पढ़ा और डिग्री 5 के शीर्ष के तर्क में एक घातक तार्किक छलांग खोज निकाली।

केम्पे ने परोक्ष रूप से यह मान लिया था कि जब दो केम्पे श्रृंखलाओं (उदाहरण के लिए, नीली-हरी श्रृंखला और नीली-पीली श्रृंखला) को अलग-अलग उलटा जाता है, तो उन्हें एक-दूसरे से स्वतंत्र रूप से उलटा जा सकता है। हालाँकि, हीवुड ने ज्यामितीय रूप से और सख्ती से सिद्ध किया कि यदि ये 2 श्रृंखलाएँ कुछ शीर्ष साझा करती हैं, तो पहली श्रृंखला को उलटने से ग्राफ की रंग स्थिति बदल जाती है, जिससे दूसरी श्रृंखला की कनेक्टिविटी (जुड़ाव) बदल जाती है।

हीवुड ने एक विशिष्ट प्रति-उदाहरण ग्राफ का निर्माण किया (जिसे अब ‘हीवुड का प्रति-उदाहरण (Heawood graph)’ या इसके व्युत्पन्न (derivatives) के रूप में जाना जाता है, जो 25 शीर्षों वाला एक अधिकतम समतल ग्राफ है)। इस ग्राफ में, जब डिग्री 5 के शीर्ष $v$ के आस-पास के रंगों को कम करने के लिए केम्पे के एल्गोरिदम को लागू किया गया, तो नीली-हरी श्रृंखला को उलटने के क्षण ही, पहले से असंबद्ध नीली-पीली श्रृंखला जुड़ गई, और उसके बाद नीली-पीली श्रृंखला को उलटने से पहले उलटे गए हरे शीर्ष फिर से अपने मूल रंग में वापस आ गए, जिसके परिणामस्वरूप रंगों की संख्या कम न होने का एक लूप (loop) बन गया।

केम्पे की ‘दोहरी केम्पे श्रृंखलाओं की एक साथ अदला-बदली’ एक भ्रम (fallacy) थी जिसका परिणाम समतल ग्राफ के जटिल उलझावों को कम आंकना था, कि स्थानीय टोपोलॉजिकल पृथक्करण संबंध वैश्विक रूप से बनाए नहीं रखे जा सकते। इस खोज से, चार-रंग प्रमेय के लिए केम्पे का प्रमाण पूरी तरह से ढह गया।

पांच-रंग प्रमेय का पूर्ण गणितीय प्रमाण

हालाँकि केम्पे का प्रमाण विफल हो गया, हीवुड ने केवल इसे नष्ट नहीं किया। उन्होंने यह महसूस किया कि केम्पे का विचार (केम्पे श्रृंखला) अपने आप में अत्यंत उपयोगी था, और इसका उपयोग ‘पांच-रंग प्रमेय (Five Color Theorem)’ को सख्ती से सिद्ध करने के लिए किया, जो बताता है कि ‘सभी समतल ग्राफ़ को 5 रंगों का उपयोग करके रंगा जा सकता है’। पांच-रंग प्रमेय की पूर्ण प्रमाण प्रक्रिया इस प्रकार है:

प्रमेय: कोई भी समतल ग्राफ $G$, 5 रंगों से शीर्ष-रंगा जा सकता है। प्रमाण: शीर्षों की संख्या $n$ पर गणितीय आगमन का उपयोग करके। $n \leq 5$ के लिए मामला तुच्छ (trivial) है। मान लें कि $n=k$ वाले सभी समतल ग्राफ 5 रंगों से रंगे जा सकते हैं, और $n=k+1$ वाले समतल ग्राफ $G$ पर विचार करें। यूलर के सूत्र से प्राप्त तथ्य के अनुसार, $G$ में हमेशा 5 या उससे कम डिग्री वाला एक शीर्ष $v$ मौजूद होता है। $G$ से $v$ को हटाकर प्राप्त ग्राफ $G' = G - \{v\}$ में शीर्षों की संख्या $k$ है, इसलिए आगमन परिकल्पना द्वारा इसे 5 रंगों (रंग 1, रंग 2, रंग 3, रंग 4, रंग 5) से रंगा जा सकता है। अब हम $G'$ के रंग को बनाए रखते हुए $v$ को वापस लाने पर विचार करते हैं।

स्थिति 1: यदि $\deg(v) < 5$ है。 $v$ के आसन्न शीर्ष अधिकतम 4 हैं, इसलिए 5 रंगों में से कम से कम 1 रंग का उपयोग आसन्न शीर्षों पर नहीं किया गया है। हम $v$ पर उस रंग का उपयोग कर सकते हैं।
स्थिति 2: यदि $\deg(v) = 5$ है。 मान लें कि $v$ के 5 आसन्न शीर्ष $v_1, v_2, v_3, v_4, v_5$ (दक्षिणावर्त व्यवस्थित) सभी अलग-अलग रंगों (क्रमशः रंग 1, रंग 2, रंग 3, रंग 4, रंग 5) से रंगे गए हैं। (यदि किसी रंग का 2 या अधिक बार उपयोग किया गया है, तो कम से कम 1 रंग अप्रयुक्त बचेगा जिसे $v$ पर रंगा जा सकता है)। यहाँ, ग्राफ $G'$ में, केवल रंग 1 और रंग 3 से रंगे शीर्षों वाले प्रेरित उप-ग्राफ (induced subgraph) पर विचार करें, और $v_1$ वाले जुड़े घटक को $C_{13}$ मान लें (यह एक केम्पे श्रृंखला है)।
- उप-स्थिति 2a: यदि $v_3 \notin C_{13}$ है。 अर्थात्, यदि $v_1$ से $v_3$ तक केवल रंग 1 और रंग 3 वाले शीर्षों से होकर जाने वाला कोई मार्ग (path) मौजूद नहीं है। इस समय, $C_{13}$ के सभी शीर्षों के रंगों को उलटने (रंग 1 $\leftrightarrow$ रंग 3) पर भी रंग की वैधता बनी रहती है। उलटने के बाद, $v_1$ रंग 3 बन जाता है, और चूँकि $v_3$ भी रंग 3 है, इसलिए $v$ के आस-पास रंग 1 मौजूद नहीं रहेगा। इसलिए $v$ को रंग 1 से रंगा जा सकता है।
- उप-स्थिति 2b: यदि $v_3 \in C_{13}$ है。 अर्थात्, यदि $v_1$ और $v_3$ को जोड़ने वाला रंग 1 और रंग 3 के शीर्षों का मार्ग $P_{13}$ मौजूद है। यह मार्ग $P_{13}$ शीर्ष $v$, और किनारों $(v, v_1), (v, v_3)$ के साथ मिलकर समतल पर एक बंद वक्र (चक्र - cycle) बनाता है। समतल ग्राफ के गुण (जॉर्डन कर्व थ्योरम) के अनुसार, यह चक्र समतल को अंदर और बाहर के हिस्सों में विभाजित करता है। शीर्ष $v_2$ और $v_4$ इस चक्र के अलग-अलग तरफ (एक अंदर, एक बाहर) स्थित हैं। यहाँ, रंग 2 और रंग 4 से रंगे शीर्षों वाली केम्पे श्रृंखला $C_{24}$ पर विचार करें। यदि हम मान लें कि $v_2$ और $v_4$ इस श्रृंखला द्वारा जुड़े हुए हैं, तो $v_2$ और $v_4$ को जोड़ने वाला मार्ग $P_{24}$ मौजूद होना चाहिए। हालाँकि, $P_{24}$ को बिना पार किए समतल ग्राफ पर चलना चाहिए, लेकिन यह $P_{13}$ द्वारा बनाए गए चक्र को पार नहीं कर सकता है (यह समतल ग्राफ की परिभाषा के विरुद्ध होगा)। इसलिए, $v_2$ और $v_4$ को जोड़ने वाला रंग 2 और रंग 4 का मार्ग बिल्कुल भी मौजूद नहीं हो सकता है। अर्थात्, $v_2$ वाली रंग 2-रंग 4 की केम्पे श्रृंखला $C_{24}$ में $v_4$ शामिल नहीं है। इसलिए, यदि हम $C_{24}$ में रंगों को उलटते (रंग 2 $\leftrightarrow$ रंग 4) हैं, तो $v_2$ रंग 4 बन जाएगा, और रंग 2, $v$ के आस-पास से गायब हो जाएगा। अंततः, $v$ को रंग 2 से रंगा जा सकता है।

उपरोक्त आधार पर, किसी भी स्थिति में $v$ को रंगा जा सकता है, और गणितीय आगमन द्वारा पांच-रंग प्रमेय पूरी तरह से सिद्ध हो गया है। $\blacksquare$

यह प्रमाण समतल ग्राफ के टोपोलॉजी (जॉर्डन कर्व थ्योरम) का बहुत ही सुंदर तरीके से उपयोग करता है, और यह दर्शाता है कि एक एकल गैर-प्रतिच्छेदी श्रृंखला के अनुप्रयोग में केम्पे की ‘केम्पे श्रृंखला’ की अवधारणा कितनी मजबूत है। हालाँकि, ‘4 रंगों’ का मार्ग यहाँ से ‘कम करने की क्षमता (Reducibility)’ और ‘अपरिहार्य सेट (Unavoidable Set)’ के नए प्रतिमानों (paradigms) से होकर गुजरेगा, और भारी गणनाओं के समुद्र में प्रवेश करेगा।

अध्याय 3: डिस्चार्जिंग विधि (Discharging Method) का गणित और अपरिहार्य विन्यासों की व्युत्पत्ति (Derivation)

हीवुड के बाद, गणितज्ञों ने यह मानना शुरू कर दिया कि ‘चार रंगों से न रंगा जा सकने वाला सबसे छोटा प्रति-उदाहरण (Minimum Counterexample)’ मौजूद है, और उन्होंने विरोधाभास द्वारा यह पता लगाना शुरू किया कि इसमें किस प्रकार की संरचना होनी चाहिए (या नहीं होनी चाहिए)। यहाँ दो शक्तिशाली अवधारणाएँ महत्वपूर्ण हो जाती हैं: ‘कम करने योग्य विन्यास (Reducible Configuration)’ और ‘अपरिहार्य सेट (Unavoidable Set)’।

कम करने की क्षमता (Reducibility)

कम करने योग्य विन्यास शीर्षों की एक स्थानीय उप-संरचना (पैटर्न) है जो ‘यदि पूरा ग्राफ चार रंगों से रंगा नहीं जा सकता (सबसे छोटा प्रति-उदाहरण है), तो वह ग्राफ में कभी मौजूद नहीं हो सकता’। उदाहरण के लिए, ‘3 या उससे कम डिग्री वाले शीर्ष’ या ‘4 डिग्री वाले शीर्ष’ कम करने योग्य विन्यास हैं। इसका कारण यह है कि जैसा कि पहले उल्लेख किया गया है, यदि केम्पे श्रृंखला द्वारा कमी का उपयोग किया जाता है, तो अगर वे मौजूद होते, तो समस्या को छोटे ग्राफ की समस्या में बदला (कम किया) जा सकता था, जो ‘सबसे छोटे प्रति-उदाहरण’ होने की धारणा का खंडन करेगा। 1913 में, जॉर्ज डेविड बिरखॉफ (George David Birkhoff) ने सिद्ध किया कि 6 शीर्षों वाला एक विशिष्ट विन्यास जिसे ‘बिरखॉफ का हीरा (Birkhoff’s diamond)’ कहा जाता है, वह भी कम करने योग्य है। हालांकि कम करने योग्य विन्यासों की खोज आगे बढ़ी, लेकिन अगर यह गारंटी नहीं दी जा सकती कि वे ग्राफ में ‘हमेशा मौजूद’ होते हैं, तो प्रमाण पूरा नहीं हो सकता।

डिस्चार्जिंग विधि (Discharging Method) की गणितीय संरचना

चार-रंग प्रमेय को सिद्ध करने की अंतिम रणनीति ‘एक अपरिहार्य सेट ढूँढना है, जो पूरी तरह से कम करने योग्य विन्यासों से बना हो’। एक अपरिहार्य सेट विन्यासों की एक सूची है जहाँ ‘कोई भी समतल ग्राफ (अधिक सटीक रूप से अधिकतम समतल ग्राफ) उस सूची में कम से कम एक विन्यास को अवश्य शामिल करेगा’।

इस अपरिहार्य सेट के निर्माण और इसे सिद्ध करने के लिए एक अत्यंत शक्तिशाली हथियार है ‘डिस्चार्जिंग विधि (Discharging Method)’, जिसे हेनरिक हेश (Heinrich Heesch) द्वारा परिष्कृत किया गया था। डिस्चार्जिंग विधि ग्राफ सिद्धांत में संरचनात्मक प्रमेयों को सिद्ध करने के लिए एक जादुई तकनीक है, जो इलेक्ट्रोमैग्नेटिज्म में चार्ज की अवधारणा को एक सादृश्य (analogy) के रूप में उपयोग करती है।

डिस्चार्जिंग विधि की गणितीय प्रक्रिया इस प्रकार है:

$$ch(v) = 6 - \deg(v)$$
यूलर के सूत्र से प्राप्त समीकरण $\sum_{v} (6 - \deg(v)) = 12$ के अनुसार, पूरे ग्राफ का कुल प्रारंभिक चार्ज ठीक 12 (एक सकारात्मक मूल्य) होता है। इस मामले में, डिग्री 5 वाले शीर्षों का चार्ज $+1$ होता है, डिग्री 6 वालों का $0$ होता है, और डिग्री 7 या उससे अधिक वालों का नकारात्मक चार्ज होता है। (चूंकि यह माना जा सकता है कि सबसे छोटे प्रति-उदाहरण में डिग्री 4 या उससे कम वाले शीर्ष मौजूद नहीं हैं, हम न्यूनतम डिग्री 5 मानते हैं)।
चार्ज स्थानांतरण नियम (Discharging Rules) को परिभाषित करना: अगला कदम आसन्न शीर्षों के बीच चार्ज स्थानांतरित करने के नियमों को परिभाषित करना है। मूल विचार है ‘सकारात्मक चार्ज वाले शीर्षों (अर्थात् डिग्री 5 वाले शीर्ष) से नकारात्मक चार्ज वाले शीर्षों (डिग्री 7 या उससे अधिक वाले उच्च-डिग्री शीर्ष) में चार्ज प्रवाहित करना (डिस्चार्ज करना)’। उदाहरण के लिए, ‘यदि डिग्री 5 का शीर्ष $v$ डिग्री 7 के शीर्ष $u$ के आसन्न है, तो $v$ से $u$ में $\frac{1}{5}$ चार्ज स्थानांतरित करें’ जैसे सैकड़ों नियमों को बहुत सूक्ष्मता से सेट किया जाता है।
$$ \sum_{v \in V} ch'(v) = 12 > 0 $$
($ch'(v)$ स्थानांतरण के बाद शीर्ष $v$ का चार्ज है) कुल योग का सकारात्मक होने का मतलब है कि ‘चार्ज के स्थानांतरण के बाद भी कम से कम एक सकारात्मक चार्ज वाला शीर्ष मौजूद होना चाहिए’।
यहाँ, प्रत्येक शीर्ष के अंतिम चार्ज $ch'(v)$ का विश्लेषण उसकी स्थानीय संरचना (उसके और उसके आसन्न शीर्षों के डिग्री पैटर्न) के आधार पर किया जाता है। यदि यह सिद्ध किया जा सके कि ‘एक निश्चित विन्यास के बिना किसी शीर्ष का अंतिम चार्ज स्थापित डिस्चार्जिंग नियमों के तहत हमेशा शून्य या उससे कम होगा’, तो अंतिम चार्ज सकारात्मक होने के लिए, वह ‘निश्चित विन्यास’ ग्राफ में कहीं न कहीं अवश्य मौजूद होना चाहिए। इस प्रकार, स्थानीय विन्यास पैटर्न की एक विस्तृत सूची, जिसके परिणामस्वरूप अंतिम चार्ज सकारात्मक होगा, ‘अपरिहार्य सेट’ बन जाती है।

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

अध्याय 4: 1976, अपेल और हाकेन का कंप्यूटर सत्यापन एल्गोरिदम

D-reduction और C-reduction की परिभाषा

1970 के दशक में, इलिनोइस विश्वविद्यालय के केनेथ अपेल (Kenneth Appel) और वोल्फगैंग हाकेन (Wolfgang Haken) ने हेश की डिस्चार्जिंग विधि को कंप्यूटर की कंप्यूटिंग शक्ति के साथ संयोजित करने के लिए एक ऐतिहासिक परियोजना शुरू की।

उनके द्वारा किया गया सबसे अधिक कम्प्यूटेशनल कार्य विन्यासों की ‘कम करने की क्षमता का परीक्षण’ था। कम करने की क्षमता (Reducibility) मुख्य रूप से 2 प्रकार की होती है।

D-कम करने की क्षमता (D-reducibility / Direct reducibility): विन्यास को घेरने वाली रिंग सीमा (Ring) के सभी संभावित 4-रंग पैटर्न के लिए, क्या इसे विन्यास के अंदर भी विस्तारित करके रंगा जा सकता है, या क्या सीमा के रंगों के केम्पे श्रृंखला को उलट कर इसे एक ऐसे पैटर्न में परिवर्तित किया जा सकता है जिसे अंदर विस्तारित किया जा सकता है। यदि इसकी पुष्टि की जा सकती है, तो यह तुरंत कहा जा सकता है कि विन्यास सबसे छोटे प्रति-उदाहरण में शामिल नहीं है।
C-कम करने की क्षमता (C-reducibility / Contracting reducibility): यदि ऐसा कोई पैटर्न है जो D-कम करने की क्षमता के परीक्षण में विफल रहता है, तो विन्यास के एक हिस्से को ‘अनुबंधित (contracting - कई शीर्षों को एक में मिलाना)’ करके एक छोटा ग्राफ माना जाता है, और यह दिखाने की विधि कि यदि वह अनुबंधित ग्राफ 4 रंगों से रंगा जा सकता है, तो मूल ग्राफ भी 4 रंगों से रंगा जा सकता है।

रिंग सीमा के रंगने की संभावना निर्धारित करने के लिए एल्गोरिदम

कंप्यूटर (IBM 360) को विन्यास उम्मीदवारों की एक बड़ी संख्या के लिए D-कम करने की क्षमता और C-कम करने की क्षमता का परीक्षण करने वाले एल्गोरिदम को चलाने का काम सौंपा गया था।

मान लें कि एक विन्यास $C$ की एक सीमा रिंग $R$ (लंबाई $k$) है। रिंग पर शीर्षों को 4 रंगों से रंगने के अधिकतम $4^k$ संयोजन हैं, जो समरूपता (symmetry) पर विचार करने के बाद भी एक बड़ी संख्या है। उदाहरण के लिए, यदि रिंग की लंबाई $k=14$ है, तो लगभग 200,000 सीमा रंग संयोजनों की वैधता की जांच करने की आवश्यकता है। एल्गोरिदम निम्न चरणों के अनुसार आगे बढ़ता है।

सीमा रिंग $R$ के सभी वैध 4-रंग पैटर्न का सेट उत्पन्न करें।
विन्यास $C$ के अंदर के हिस्से को 4 रंगों से रंगने के सभी तरीकों का प्रयास करें, और रिकॉर्ड करें कि कौन से सीमा पैटर्न संगत (compatible/internally extensible) हैं।
उन सीमा पैटर्नों के लिए जिन्हें आंतरिक रूप से विस्तारित नहीं किया जा सकता है, केम्पे श्रृंखला उलटाव का अनुकरण (simulate) करें। यदि उलटाव एक ऐसे पैटर्न में बदल सकता है जो पहले से ही ‘आंतरिक रूप से विस्तार योग्य’ के रूप में जाना जाता है, तो प्रारंभिक पैटर्न को भी ‘हल (resolved)’ माना जाता है।
इस उलटाव संक्रमण की खोज को दोहराएँ, और यदि सभी सीमा पैटर्न हल किए जा सकते हैं, तो विन्यास $C$ को ‘D-कम करने योग्य’ माना जाता है।

चूँकि सीमा की लंबाई बढ़ने पर गणना का समय अत्यधिक बढ़ जाता है, अपेल और हाकेन ने विन्यासों को अधिकतम 14 की रिंग लंबाई तक सीमित कर दिया, और इसके भीतर एक अपरिहार्य सेट बनाने के लिए डिस्चार्जिंग नियमों को पूरी तरह से ट्यून किया। यह ट्यूनिंग प्रक्रिया स्वयं मनुष्य और कंप्यूटर के बीच परीक्षण और त्रुटि (trial and error) की एक बड़ी श्रृंखला थी। ‘मनुष्य डिस्चार्जिंग नियमों को संशोधित करता है, कंप्यूटर अपरिहार्य सेट के उम्मीदवारों का उत्पादन करता है, कम करने की क्षमता का परीक्षण करता है, और विफल होने वाले विन्यासों को देखने के बाद मनुष्य फिर से नियमों को संशोधित करता है’ - यह संवादात्मक प्रक्रिया कई वर्षों तक जारी रही।

1200 घंटे की गणना और “Q.E.D.”

1976 में, उन्होंने अंततः एक अपरिहार्य सेट खोजा जिसमें सावधानीपूर्वक निर्मित डिस्चार्जिंग नियमों द्वारा प्राप्त किए गए 1,936 विन्यास शामिल थे। और इलिनोइस विश्वविद्यालय के मेनफ्रेम को 1200 से अधिक घंटों तक चलाने के बाद, कंप्यूटर ने पुष्टि की कि सभी 1,936 विन्यास D-कम करने योग्य या C-कम करने योग्य हैं।

उन्होंने अपने पेपर के सार (abstract) में संक्षेप में लिखा: “Every planar map is four colorable.” (हर समतल मानचित्र चार रंगों से रंगा जा सकता है।)

इलिनोइस विश्वविद्यालय के गणित विभाग के डाक टिकट पर गर्व से उकेरा गया: ‘FOUR COLORS SUFFICE (4 रंग पर्याप्त हैं)’। यह गणित के इतिहास में एक स्मारकीय घटना थी जहाँ एक कंप्यूटर ने प्रमेय के प्रमाण में मुख्य डिडक्टिव कदम (deductive step) को अंजाम दिया था।

अध्याय 5: गणितीय दुनिया में सदमा और “प्रमाण” का दर्शन

अपेल और हाकेन की घोषणा ने गणितीय समुदाय में खुशी से ज्यादा गहरा भ्रम और तीखी बहस पैदा कर दी।

क्या एक प्रमाण जिसे मनुष्य नहीं पढ़ सकते, गणित है?

प्राचीन ग्रीस से चली आ रही गणितीय परंपरा में, ‘प्रमाण’ कुछ ऐसा था जिसमें एक मानव गणितज्ञ तर्क के चरणों का एक-एक करके अनुसरण कर सकता था, और उसकी शुद्धता को गहराई से समझकर उससे सहमत हो सकता था। यह माना जाता था कि प्रमाण की प्रक्रिया में ‘यह प्रमेय क्यों सत्य है’ इसकी गहरी समझ और संरचनात्मक सुंदरता निहित होती है।

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

एक अभूतपूर्व स्थिति उत्पन्न हुई: ‘प्रमाण के सही होने पर विश्वास करने के लिए, आपको यह विश्वास करना होगा कि कंप्यूटर के हार्डवेयर में कोई खराबी नहीं है और अपेल और हाकेन द्वारा लिखे गए असेंबली भाषा कार्यक्रम में कोई बग (bug) नहीं है’।

विज्ञान के दार्शनिक थॉमस टिमोक्ज़को (Thomas Tymoczko) ने आलोचना की कि क्या यह प्रमाण शुद्ध गणित की प्राथमिक (a priori) सत्य की खोज से भौतिकी की तरह अनुभवजन्य विज्ञान और प्रायोगिक (empirical and experimental) चीज़ में गिर गया है। ‘प्रमाण’ की परिभाषा का कार्य ही ज्ञानमीमांसीय संकट (epistemological crisis) में पड़ गया।

प्रतिवाद और RSST द्वारा सरलीकरण

अपेल और हाकेन ने आलोचना का यह कहते हुए जवाब दिया: ‘केवल सुंदर प्रमाण ही गणित नहीं हैं। ऐसे स्वाभाविक रूप से जटिल समस्याएँ हैं जिनके लिए बड़े पैमाने पर केस विश्लेषण की आवश्यकता होती है, और यदि यह मानव मस्तिष्क की सीमाओं से अधिक है, तो मशीन की शक्ति का सहारा लेना एक अपरिहार्य विकास है’।

इस दुविधा को दूर करने के लिए, कई गणितज्ञों ने प्रमाण को सरल बनाने और पुनः सत्यापित करने का प्रयास किया। 1997 में, नील रॉबर्टसन (Neil Robertson), डैनियल पी. सैंडर्स (Daniel P. Sanders), पॉल सेमुर (Paul Seymour), और रॉबिन थॉमस (Robin Thomas) (आमतौर पर RSST के रूप में जाने जाते हैं) ने एक नया प्रमाण प्रकाशित किया जिसने डिस्चार्जिंग विधि को अधिक व्यवस्थित और मानव-सत्यापन योग्य बना दिया, और अपरिहार्य सेट के आकार को 1,936 से घटाकर 633 कर दिया। यह एक परिष्कृत एल्गोरिदम था जिसकी गणना कुछ घंटों में ही पूरी हो जाती थी।

हालाँकि, यह अभी भी ‘कंप्यूटर द्वारा कम करने की क्षमता की गणना’ पर निर्भर था। ‘कागज और कलम का सुंदर प्रमाण’ जिसे मानव अंतर्ज्ञान से पूरी तरह समझा जा सकता हो, अभी तक नहीं मिला है (और कई ग्राफ सिद्धांतकारों का मानना है कि ऐसा प्रमाण सैद्धांतिक रूप से मौजूद नहीं हो सकता है)।

अध्याय 6: Coq का उपयोग करके जॉर्जेस गोंथियर द्वारा पूर्ण औपचारिक प्रमाण

हम इस आशंका को पूरी तरह से कैसे दूर कर सकते हैं कि ‘प्रोग्राम में बग हो सकता है’? इसका अंतिम उत्तर ‘प्रमेय प्रमाणक सहायक (Proof Assistant)’ का उपयोग करके पूर्ण औपचारिकीकरण (Formalization) है।

2005 में, फ्रेंच नेशनल इंस्टीट्यूट फॉर रिसर्च इन कंप्यूटर साइंस एंड कंट्रोल (INRIA) और माइक्रोसॉफ्ट रिसर्च के जॉर्जेस गोंथियर (Georges Gonthier) ने बेंजामिन वर्नर (Benjamin Werner) के साथ मिलकर प्रमेय प्रमाणक सहायक ‘Coq’ का उपयोग करके चार-रंग प्रमेय के प्रमाण को मौलिक रूप से पूरी तरह औपचारिक बनाने में सफलता प्राप्त की।

हाइपरमैप (Hypermap) और कॉम्बिनेटोरियल टोपोलॉजी का औपचारिकीकरण

Coq एक प्रणाली है जो गणितीय स्वयंसिद्धों (axioms) से शुरू होती है और नियमों की एक अत्यंत सख्त तार्किक प्रणाली (Calculus of Inductive Constructions) के अनुसार प्रमाणों का वर्णन और मशीनी-सत्यापन करती है।

गोंथियर की सबसे बड़ी उपलब्धि समतल ग्राफ की सहज और ज्यामितीय वस्तुओं को पूरी तरह से बीजीय (algebraic) और कॉम्बिनेटोरियल संरचना में अनुवादित करना था जिसे कंप्यूटर संभाल सकता है। उन्होंने ग्राफ के शीर्षों, किनारों और फलकों के संबंधों को दर्शाने के लिए ‘हाइपरमैप (Hypermap)’ नामक एक डेटा संरचना को परिभाषित किया। यह ग्राफ को ‘डार्ट्स (आधे किनारों)’ के एक सेट और उन पर क्रमपरिवर्तन (permutation) समूहों के रूप में प्रस्तुत करने की एक विधि है। इसके परिणामस्वरूप, यूलर के सूत्र और जॉर्डन कर्व थ्योरम जैसे टोपोलॉजिकल प्रमेयों को समूह सिद्धांत और परिमित सेट कॉम्बिनेटोरियल तर्क के रूप में पूरी तरह से औपचारिक बना दिया गया।

प्रमाण प्रोग्राम की अपनी शुद्धता का प्रमाण

इसके अलावा, गोंथियर ने अपेल-हाकेन और RSST द्वारा उपयोग किए जाने वाले ‘C भाषा में लिखे गए सत्यापन प्रोग्राम’ को छोड़ दिया, और कम करने की क्षमता को निर्धारित करने वाले एल्गोरिदम को सीधे Coq की आंतरिक भाषा (Gallina) का उपयोग करके लागू किया। और, उन्होंने Coq पर गणितीय रूप से इस एल्गोरिदम की शुद्धता को ही सिद्ध किया कि ‘यदि यह判定 एल्गोरिदम “True” आउटपुट देता है, तो वह विन्यास वास्तव में कम करने योग्य है’।

इसने प्रमाण की विश्वसनीयता को निर्णायक रूप से बदल दिया। अब ‘एल्गोरिदम में बग’ के बारे में चिंता करने की कोई आवश्यकता नहीं थी। क्योंकि, जब तक Coq का मुख्य तर्क सत्यापन कर्नेल (सैकड़ों पंक्तियों का एक अत्यंत सरल और पुराना कोड, जिसे डी ब्रुजन इंडेक्स आदि का उपयोग करके लागू किया गया है) तार्किक अनुमान नियमों को सही ढंग से संसाधित कर रहा है, तब तक गोंथियर द्वारा बनाए गए विशाल प्रमाण वृक्ष के पूर्णतः सत्य होने की गणितीय गारंटी है।

यह गणित में ‘प्रमाण’ का एक नया मुकाम है। यह ‘मनुष्यों द्वारा पढ़े और समझे जाने वाले प्रमाण (Informal Proof)’ से ‘मशीनों द्वारा तार्किक पूर्णता की गारंटी वाले औपचारिक प्रमाण (Formal Proof)’ तक का विकास है। चार-रंग प्रमेय इतिहास का पहला गैर-तुच्छ (non-trivial) प्रमुख प्रमेय बन गया जो कठोरता के इस चरम स्तर तक पहुँचा।

अध्याय 7: समतल ग्राफ की 4-रंग समस्या और NP-पूर्णता का विरोधाभास

अंत में, आइए चार-रंग प्रमेय को कम्प्यूटेशनल जटिलता सिद्धांत (Computational Complexity Theory) के दृष्टिकोण से देखें। यहाँ एक बहुत ही दिलचस्प विरोधाभास जैसी घटना मौजूद है।

सामान्य ग्राफ़ में रंगने की समस्या (यह निर्धारित करने की समस्या कि क्या दिया गया ग्राफ $k$ रंगों से रंगा जा सकता है) कंप्यूटर विज्ञान में सबसे प्रसिद्ध ‘NP-पूर्ण (NP-complete)’ समस्याओं में से एक है। विशेष रूप से, ‘समतल ग्राफ की 3-रंग समस्या (Planar 3-Colorability)’ को NP-पूर्ण सिद्ध किया गया है। दूसरे शब्दों में, यह माना जाता है कि कोई भी एल्गोरिदम जो बहुपद समय (polynomial time) में यह निर्धारित कर सके कि क्या किसी समतल ग्राफ को 3 रंगों से रंगा जा सकता है, मौजूद नहीं है जब तक कि $\text{P} = \text{NP}$ न हो।

तो, ‘समतल ग्राफ की 4-रंग समस्या (Planar 4-Colorability)’ के बारे में क्या? चूंकि 3-रंग NP-पूर्ण है, इसलिए सहज रूप से यह लग सकता है कि 4-रंग भी उतना ही कठिन (NP-पूर्ण) होना चाहिए।

लेकिन आश्चर्यजनक रूप से, समतल ग्राफ की 4-रंग समस्या (निर्णय समस्या - Decision Problem) की कम्प्यूटेशनल जटिलता $O(1)$ है, जिसका अर्थ है ‘निरंतर समय (constant time/तुच्छ)’। कारण यह है कि, क्योंकि चार-रंग प्रमेय गारंटी देता है कि ‘सभी समतल ग्राफ को 4 रंगों से रंगा जा सकता है’, एल्गोरिदम को इनपुट ग्राफ को देखने की भी आवश्यकता नहीं है; यह केवल ‘Yes’ आउटपुट कर सकता है और हमेशा 100% सही होगा। यह इस बात का एक सुंदर उदाहरण है कि कैसे किसी प्रमेय की शक्तिशाली अस्तित्व गारंटी किसी निर्णय समस्या की जटिलता को उसकी चरम सीमा तक कम कर सकती है।

हालाँकि, यह केवल ‘रंगा जा सकता है या नहीं’ की निर्णय समस्या (Decision Problem) के बारे में है। ‘वास्तव में 4 रंगों से कैसे रंगा जाए’ इसका एक रंगने वाला एल्गोरिदम (Search Problem) बनाना एक अलग बात है। यदि अपेल-हाकेन या RSST की प्रमाण प्रक्रियाओं को एक एल्गोरिदम के रूप में लागू किया जाता है, तो $N$ शीर्षों वाले दिए गए समतल ग्राफ के लिए वास्तविक 4-रंग की व्यवस्था खोजने के लिए एक एल्गोरिदम प्राप्त किया जा सकता है। RSST के प्रमाण पर आधारित एल्गोरिदम को सबसे खराब स्थिति में $O(N^2)$ के बहुपद समय में 4-रंग आउटपुट करने के लिए दिखाया गया है।

अर्थात्, जबकि किसी समतल ग्राफ को 3 रंगों से रंगने में ब्रह्मांड के जीवनकाल जितना समय लग सकता है (NP-पूर्ण), 4था रंग जोड़ते ही, चार-रंग प्रमेय के पीछे की गणितीय संरचना के आशीर्वाद के कारण, एक तेज़ ($O(N^2)$) एल्गोरिदम अस्तित्व में आ जाता है। यह गणित और कंप्यूटर विज्ञान के चौराहे पर एक अत्यंत रहस्यमय और आकर्षक तथ्य है।

निष्कर्ष: चार-रंग प्रमेय ने क्या पीछे छोड़ा

1852 में एक युवा ब्रिटिश व्यक्ति द्वारा मानचित्र को रंगने की एक साधारण समस्या मात्र एक पहेली के रूप में शुरू हुई थी। हालाँकि, एक सदी से अधिक समय के बाद, इसने ग्राफ सिद्धांत नामक गणित के एक विशाल नए क्षेत्र का मार्ग प्रशस्त किया, एल्गोरिदम सिद्धांत को विकसित किया, और अंततः मानवता के सामने मूलभूत दार्शनिक प्रश्न खड़े किए: ‘क्या कंप्यूटर गणितीय प्रमाण कर सकते हैं?’ और ‘गणितीय सत्य क्या है?’।

चार-रंग प्रमेय का इतिहास मानव अंतर्ज्ञान की सीमाओं और मशीन नामक एक नए तार्किक इंजन की संभावनाओं के बीच भयंकर टकराव का इतिहास है। आज, अन्य विशाल कठिन समस्याओं, जैसे कि केप्लर का अनुमान (2014, थॉमस हेल्स द्वारा फ्लाईस्पेक प्रोजेक्ट) और फ़ीट-थॉम्पसन प्रमेय, को भी प्रमेय प्रमाणक सहायकों का उपयोग करके औपचारिक सत्यापन द्वारा पूरी तरह से सिद्ध किया जा चुका है।

जब हम लापरवाही से किसी मानचित्र को 4 रंगों से रंगते हैं, तो यूलर के बहुफलक का सौंदर्यशास्त्र, केम्पे की प्रतिभाशाली विफलता, हीवुड का कठोर खंडन, हेश के डिस्चार्जिंग का गणित, हजारों घंटों तक चमकते सुपरकंप्यूटरों की गणना का प्रक्षेपवक्र (trajectory), और Coq के हाइपरमैप का तर्क उस पृष्ठभूमि में कई परतों में छिपा होता है। चार-रंग प्रमेय को इस बात के सर्वश्रेष्ठ केस स्टडी के रूप में याद किया जाएगा कि कैसे गणित मानव विचार की सीमाओं को पार करके अपना विस्तार करता है।