1960 دے دہاکے دی اک گراف بُجھارت آخر مُک گئی

کجھ نقطے لوو تے اوہناں دے کجھ جوڑیاں نوں لکیراں نال جوڑو: ریاضی دان ایہنوں گراف (graph) آکھدے نیں، نقطیاں نوں ایہدے راس (vertices) تے لکیراں نوں ایہدے کنارے (edges)۔ اک سائیکل (cycle) اک بند گول اے جیہڑا وکھرے وکھرے راساں توں لنگھدا اے تے جتھوں ٹریا سی اوتھے مڑ آندا اے۔ اک قدرتی سوال ایہ اے پئی کیہ کسے گراف دے کنارے — ہر کنارہ ٹھیک اک واری ورت کے — سائیکلاں وچ ونڈے جا سکدے نیں۔

جیویں مقالہ یاد کراندا اے، جواب چِر توں پتہ اے: ایہ عین اوس ویلے ممکن اے جدوں ہر راس جفت گنتی دے کناریاں نوں چھوہندا ہووے۔ اجیہے گرافاں نوں اویلری (Eulerian) آکھدے نیں۔ اگلا سوال ایہ اے پئی کنے سائیکل چاہیدے نیں۔ تے جیہناں گرافاں لئی صرف سائیکل کافی نہیں، اوتھے اکلے کناریاں نوں وی ٹکڑیاں وانگوں منیا جاندا اے۔

اندازہ (حدس)

1960 دے دہاکے وچ، ایردوش تے گالائی (Erdős, Gallai) نے اندازہ لایا پئی n راساں والے ہر گراف دے کنارے اینے سائیکلاں تے اکلے کناریاں وچ ونڈے جا سکدے نیں جیہڑے ودھ توں ودھ n دے حساب نال ہون — جیہنوں O(n) لکھیا جاندا اے۔ ایردوش نے ایہنوں اپنے حل نہ ہوئے مسئلیاں دے کئی مجموعیاں وچ رلایا۔ ہایوش (Hajós) دا اک جُڑیا اندازہ ہر اویلری گراف وچ ودھ توں ودھ (n − 1)/2 سائیکل منگدا اے۔

سدھا (linear) ہونا سب توں چنگی امید اے: ایردوش نے وکھایا پئی کجھ گرافاں نوں لگ بھگ 1.5 n ٹکڑے چاہیدے نیں۔ سوال ایہ سی پئی کیہ n دا کوئی مستقل گنا ہمیشہ کافی اے۔

ہولی ہولی کھسکدیاں حداں دے پنجاہ ورھے

ایردوش تے گالائی نے آپ اک سوکھا طریقہ ویکھیا: بار بار سب توں لمّا سائیکل کڈھو۔ ایہ لگ بھگ n log n ٹکڑے دیندا اے — تے مقالے موجب، ایہ لگ بھگ پنجاہ ورھے سب توں چنگی عام حد رہی۔ حالیہ ویلے وچ، کونلن، فوکس تے سوداکوف نے ایہنوں n log log n تک گھٹایا، فیر بوچچ تے منٹگمری نے n log* n تک، جتھے log* n — اوہ گنتی جنی واری لوگارتھم لینا پیندا اے تاں جے اک توں تھلے آیا جاوے — سوچ توں وی ودھ ہولی ودھدا اے۔ ایہ طریقے گیڑیاں وچ کم کردے سن، تے ہر گیڑا لگ بھگ n سائیکلاں دا خرچہ کردا سی، ایس لئی گیڑیاں دی گنتی ہمیشہ آخری گنتی وچ رل جاندی سی۔ ایہ اندازہ خاص ٹبراں لئی وی ثابت ہو چکیا سی، جیویں بے ترتیب گراف (random graphs)۔

وزن جیہڑے گولاں دا مُل تاردے نیں

جنوبی کوریا دی KAIST دے جے ہون کم (Jaehoon Kim) ہُن ایہ اندازہ ثابت کردے نیں: اک پکا مستقل C موجود اے جیہدے نال n راساں والا ہر گراف ودھ توں ودھ Cn سائیکلاں تے کناریاں وچ ونڈیا جاندا اے۔ ایہدے نتیجے وچ، ہایوش دا اندازہ اک مستقل ضرب تک سچا اے۔

ثبوت گیڑیاں نوں چھڈ دیندا اے۔ اکو طریقہ سائیکل تے کنارے اک اک کر کے کڈھدا اے، تے کل گنتی دو مقداراں نال قابو وچ رہندی اے جیہناں وچوں ہر اک n دے مستقل گنے توں تھلے رہندی اے۔

• ڈگریاں اُتے ٹکی اک پوٹینشل۔ ہر راس نوں اک وزن ملدا اے جیہڑا اوہدے کناریاں دی گنتی ودھن نال گھٹدا اے، موٹے طور تے 1 / (degree × log² degree)۔ اک سائیکل بھارا اے جے اوہدے راساں دے وزناں دا جوڑ گھٹو گھٹ 1 ہووے۔ اک بھارا سائیکل کڈھن نال اک کُل “پوٹینشل” گھٹو گھٹ 1 گھٹ جاندی اے، تے ایہ پوٹینشل n دے مستقل گنے توں ودھ نال شروع نہیں ہوندی۔ ایس لئی بھارے سائیکل صرف O(n) واری کڈھے جا سکدے نیں۔
• راساں دی گنتی۔ جدوں کوئی بھارا سائیکل نہ بچے، گراف “ہولا” ہوندا اے — تے نواں مرکزی تھیورم وکھاندا اے پئی وڈیاں ڈگریاں والے ہولے گراف وچ اک سنگھنا، لگ بھگ بند علاقہ ہونا لازمی اے۔ ایہ علاقہ اپنے سائز دے حساب نال سائیکلاں تے کناریاں وچ ونڈیا جاندا اے، جیہدے مگروں اوہدے راساں دا گھٹو گھٹ پنجاہواں حصہ ودھ توں ودھ دو کناریاں نال رہ جاندا اے تے ہمیشہ لئی باہر ہو جاندا اے۔ کیوں جے ہر راس صرف اک واری باہر ہو سکدا اے، ایہ حصہ وی O(n) دا خرچہ کردا اے۔

گراف دے سنگھنے حصیاں اندر، رستیاں دے ٹکڑے “ایکسپینڈراں” وچوں لنگھدے جوڑن والے رستیاں راہیں اک سائیکل وچ بند کیتے جاندے نیں؛ اک بے ترتیب رنگائی اک سائیکل دے جوڑن والے رستیاں نوں اک دوجے توں وکھ رکھدی اے۔ — Figure 3, Kim (2026), arXiv:2610.07840.

اوہناں سنگھنے علاقیاں نوں ونڈن لئی، ثبوت بوچچ تے منٹگمری دے مضبوط “ایکسپینڈراں” — اوہ گراف جیہناں وچ راساں دے ہر ٹولے دے بہت گوانڈی ہوندے نیں — والے اوزاراں نوں ودھاندا اے، تے راساں نوں بے ترتیبی نال رنگدا اے تاں جے اکو سائیکل دے جوڑن والے رستے کدے نہ ٹکرانے۔

ہالے کیہ کھلا اے

مستقل C بہت وڈا اے، تے لکھاری نے ایہنوں بہتر بنان دی کوشش نہیں کیتی۔ سب توں چنگا مستقل لبھنا — گھٹو گھٹ 1.5 — ہالے کھلا اے، جیویں ہایوش دا ٹھیک اندازہ تے گرافاں نوں رستیاں (paths) وچ ونڈن بارے گالائی دا اک جُڑیا اندازہ۔ وزن والی چال نوں صرف اجیہے وزن چاہیدے نیں جیہناں دا جوڑ محدود رہوے (converges)، تے لکھاری صلاح دیندا اے پئی ایہ ہور ونڈ والے مسئلیاں وچ وی کم آ سکدی اے۔

ایہ اکلے لکھاری دا پری پرنٹ اے، جیہدی ہالے ہم مرتبہ جانچ نہیں ہوئی۔

مفاد دا ٹکراؤ۔ لکھاری دسدا اے پئی اوہنے دلیلاں بنان تے لکھت تے تصویراں تیار کرن وچ ChatGPT (OpenAI) تے Claude (Anthropic) دی رج کے ورتوں کیتی، تے ایہ پئی اوہنے سارے نتیجے پرکھے تے مقالے دی پوری ذمہ داری لیندا اے۔ جیہڑی لکھت تسیں پڑھ رہے او اوہ وی Claude نے لکھی اے۔