جالاں لئی اک حد، ہُن ہر ناپ لئی ثابت

کجھ بِندو لؤ تے اوہناں دے کجھ جوڑیاں نوں لکیراں نال ملاؤ۔ ریاضی دان ایہنوں گراف (graph) آکھدے نیں: بِندو اوہدے ورٹیکس (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 دا اک مینار

ایردوش (Erdős) دے مطابق، جیویں زولتان فیوریدی نے دسیا، ایہہ سوال 1960 دے دہاکے وچ اورے (Ore) دے کم تیکر جاندا اے۔ یان پلیسنک (Ján Plesník) نے 1975 وچ ایج دی حد نوں قیاس دے طور تے بیان کیتا؛ مرٹی (Murty) تے سائمن (Simon) نے وکھرے وکھرے ایہہ تجویز کیتا تے نال ایہہ جوڑیا کہ متوازن مکمل دو حصی گراف ای اکلی انتہائی صورت اے — ایس لئی مرٹی–سائمن قیاس۔ 1970 تے 1980 دے دہاکیاں وچ، c·n² ورگیاں حداں ہولی ہولی تھلے آئیاں، c ہمیشہ 1/4 دے ہور نیڑے ہوندا گیا۔

1992 وچ، فیوریدی نے ریگولیرٹی طریقیاں (regularity methods) — سیمیریدی (Szemerédi) دے ریگولیرٹی لیما توں کڈھے اوزاراں — نال ہر کافی وڈے n لئی قیاس ثابت کیتا۔ قیمت شروع دا ناپ سی: n نوں گھٹ توں گھٹ لگ بھگ 10¹⁴ اُچائی والا 2 دا اک مینار ہونا سی، یعنی 2 دی طاقت 2 دی طاقت 2…، اُتوں تھلے ول گِنیا ہویا — ہر 2 نوں اوہدے اُتے والی ہر شے دی طاقت تیکر چاڑھیا جاندا اے — ڈھیر وچ لگ بھگ 10¹⁴ دو۔ ایس ناپ توں تھلے، صرف گرافاں دے کجھ خاص ٹبر ای حل ہوئے سن۔

ایج بمقابلہ غیر حاضر ایج

نواں ثبوت، سٹینفورڈ یونیورسٹی دے شعبہ ریاضی دے سنجنا داس تے جیکب فاکس دا، 3 توں اُتے ہر n لئی کم کردا اے۔ ایہہ اک زیادہ توں زیادہ جوڑ بندی (maximal matching) ورتدا اے: ایجاں دا اک سیٹ، جنہاں وچوں کوئی دو اک ورٹیکس سانجھا نہیں کردے، جیہدے وچ کوئی ہور ایج جوڑیا نہیں جا سکدا بنا دو دے ملے۔ n ورٹیکساں اُتے اک جوڑ بندی وچ ودھ توں ودھ ⌊n/2⌋ ایج ہوندے نیں۔

مُکھ لیما: اک قطر-2-نازک گراف وچ، کسے وی زیادہ توں زیادہ جوڑ بندی لئی، جوڑ بندی توں باہر دے ایج کدی وی غیر ایجاں (non-edges) — یعنی ورٹیکساں دے اوہ جوڑے جو جُڑے نہیں — توں ودھ نہیں ہوندے۔ باقی حساب اے۔ ایجاں دی گنتی دا دُگنا ودھ توں ودھ جوڑیاں دی گنتی جمع جوڑ بندی دا ناپ اے۔ 10 ورٹیکساں نال: 45 جوڑے جمع ودھ توں ودھ 5 جوڑ بندی ایج برابر 50، ایس لئی ودھ توں ودھ 25 ایج۔ ہر n لئی، ایہہ جوڑ ٹھیک مینٹل دی چھت دا دُگنا بندا اے۔

لیما آپ اک دھیان نال کیتا حساب کتاب اے۔ اک غیر ایج نازک (critical) اے جے اکو اک دو قدماں والا راہ اوہدے سریاں نوں جوڑدا اے، جیویں شکل 1 دے سارے باراں غیر ایجاں لئی۔ لکھاری ہر نازک غیر ایج نوں اوہدے راہ دے دو ایجاں نال جوڑدے نیں تے بنن والے جال نوں جُڑے ٹکڑیاں وچ ونڈدے نیں۔ اک ٹکڑے وچ نازک غیر ایجاں نالوں ودھ توں ودھ اک ایج ودھ ہوندا اے، تے اوس وادھے والے ہر ٹکڑے دی قیمت اک غیر نازک غیر ایج نال تارنی پیندی اے۔ اوہناں نوں لبھن لئی، لکھاری وٹاندرے والے نکاس (switch exits) ورتدے نیں: ٹکڑے دا کوئی ایج یا نازک غیر ایج لؤ تے اوہدے اک سرے نوں جوڑ بندی وچ اوس سرے دے ساتھی نال وٹا دیو۔ ہر غیر نازک غیر ایج اُتے ودھ توں ودھ دو واری دعویٰ ہوندا اے، ہر وادھے والا ٹکڑا گھٹ توں گھٹ دو دعوے کردا اے، تے گنتی پوری ہو جاندی اے۔

کیہنے کیہ لبھیا

“ایہہ ثبوت بہتا اے آئی نے لبھیا، خاص طور تے GPT-5.6 Sol نے 11 اگست 2026 نوں،” لکھاری اک چھوٹے اے آئی بیان وچ لکھدے نیں۔ ماڈل نے ⌊n²/4⌋ حد دا اک پورا ثبوت لبھیا، جیہنوں اوہناں نے سادہ کیتا۔ جفت (even) گنتی دے ورٹیکساں لئی، ایہنے ایہہ وی ثابت کیتا کہ متوازن مکمل دو حصی گراف ای اکلی انتہائی صورت اے، سمنر (Sumner) دے ثابت کیتے اک حقیقت اُتے ٹیک لا کے، جو اوہناں گرافاں بارے اے جنہاں وچ ہر زیادہ توں زیادہ جوڑ بندی پوری (perfect) ہوندی اے، یعنی ہر ورٹیکس نوں ڈھکدی اے۔

طاق (odd) گنتی دے ورٹیکساں نال، کوئی جوڑ بندی پوری نہیں ہوندی، تے بہت سارے گرافاں وچ ہر زیادہ توں زیادہ جوڑ بندی ٹھیک اک ورٹیکس چھڈ دیندی اے: ماڈل دی دلیل ڈھالی نہ جا سکی۔ لکھاریاں نے برابری والی صورت دا اک وکھرا ثبوت لبھیا، جو ہر n لئی ٹھیک اے، تے مقالہ آپ لکھیا؛ GPT-6 Astra راہیں آخری پڑتال نے “کجھ نکیاں تبدیلیاں” کیتیاں۔ مقالہ اک پری پرنٹ اے، اجے ہم منصب جائزے (peer review) توں نہیں لنگھیا، تے ایہدے وچ دلیل دے کسے کمپیوٹر نال پرکھے روپ دا ذکر نہیں۔

مڑ 1907 ول

جے کوئی گراف چھت دے برابر آ جاوے، تے مُکھ نابرابری ہر زیادہ توں زیادہ جوڑ بندی لئی برابری بن جاندی اے۔ جوڑ بندیاں سیانپ نال چُن کے، لکھاری وکھاؤندے نیں کہ اجیہا گراف یا تے اک تارا (star) اے — اک ورٹیکس باقی ساریاں نال جُڑیا، ہور کجھ نہیں — یا اوہدے وچ کوئی نازک غیر ایج نہیں۔ قطر-2-نازک گراف وچ، تکون دا ہر ایج کسے نازک راہ اُتے ہوندا اے، ایس لئی نازک غیر ایج نہ ہون دا مطلب اے تکون نہ ہونا؛ تارے وچ وی کوئی نہیں۔ ایس لئی برابر آن والا گراف بے تکون اے، تے آخری قدم اوہ مسئلہ اے جیہنوں قیاس مضبوط کرن نکلیا سی: 1907 دا مینٹل دا نتیجہ، جو متوازن مکمل دو حصی گراف نوں چھت اُتے اکلا چھڈ دیندا اے۔