معمای گرافی دههٔ ۱۹۶۰ سرانجام بسته می‌شود
چند نقطه بردارید و برخی از جفت‌ها را با خط به هم وصل کنید: ریاضی‌دانان این را گراف، نقطه‌ها را رأس و خط‌ها را یال می‌نامند. یک دور (cycle) مسیر بسته‌ای است که از رأس‌های متمایز می‌گذرد و به نقطهٔ آغاز بازمی‌گردد. پرسشی طبیعی این است که آیا یال‌های یک گراف را می‌توان — با استفاده از هر یال دقیقاً یک بار — به دورها تقسیم کرد.
همان‌طور که مقاله یادآوری می‌کند، پاسخ از دیرباز شناخته شده است: این کار دقیقاً زمانی ممکن است که هر رأس با تعداد زوجی یال در تماس باشد. چنین گراف‌هایی را اویلری (Eulerian) می‌نامند. پرسش بعدی این است که چند دور لازم است. و برای گراف‌هایی که دورها به‌تنهایی کافی نیستند، یال‌های تکی هم به عنوان قطعه پذیرفته می‌شوند.
حدس
در دههٔ ۱۹۶۰، اردوش و گالای حدس زدند که یال‌های هر گراف با n رأس را می‌توان به تعدادی دور و یال تکی تقسیم کرد که حداکثر متناسب با n باشد — که به صورت O(n) نوشته می‌شود. اردوش آن را در چند مجموعه از مسائل حل‌نشده‌اش گنجاند. حدس مرتبطی از هایوش (Hajós) خواستار حداکثر (n − 1)/2 دور در هر گراف اویلری است.
خطی بودن بهترین چیزی است که می‌توان امیدش را داشت: اردوش نشان داد که برخی گراف‌ها به حدود ۱٫۵ n قطعه نیاز دارند. پرسش این بود که آیا مضربی ثابت از n همیشه کافی است.
پنجاه سال کران‌هایی که آهسته پیش می‌رفتند
خودِ اردوش و گالای متوجه روش ساده‌ای شدند: برداشتن پیاپی طولانی‌ترین دور. این روش حدود n log n قطعه به دست می‌دهد — و به گفتهٔ مقاله، تقریباً پنجاه سال بهترین کران کلی باقی ماند. اخیراً کانلن، فاکس و سوداکوف آن را به n log log n رساندند، سپس بوچیچ و مونتگومری به n log* n، که در آن log* n — تعداد دفعاتی که باید لگاریتم گرفت تا به زیر یک رسید — به‌طرزی باورنکردنی کند رشد می‌کند. این رویکردها در دورهای پیاپی کار می‌کردند و هر دوره حدود n دور هزینه داشت، بنابراین تعداد دوره‌ها همیشه به شمارش نهایی راه می‌یافت. این حدس برای خانواده‌های خاصی مانند گراف‌های تصادفی نیز اثبات شده بود.
وزن‌هایی که هزینهٔ دورها را می‌پردازند
جه‌هون کیم (Jaehoon Kim)، از KAIST در کرهٔ جنوبی، اکنون این حدس را اثبات می‌کند: ثابتی مانند C وجود دارد که هر گراف با n رأس به حداکثر Cn دور و یال تقسیم می‌شود. به عنوان نتیجه، حدس هایوش تا یک ضریب ثابت برقرار است.
این اثبات دوره‌ها را کنار می‌گذارد. یک روند واحد دورها و یال‌ها را یکی‌یکی برمی‌دارد و مجموع با دو کمیت کنترل می‌شود که هر یک زیر مضربی ثابت از n می‌ماند.
- پتانسیلی بر پایهٔ درجه‌ها. هر رأس وزنی می‌گیرد که با افزایش تعداد یال‌هایش کوچک می‌شود، تقریباً 1 / (درجه × log² درجه). یک دور سنگین است اگر وزن رأس‌هایش روی هم دست‌کم 1 شود. برداشتن یک دور سنگین یک «پتانسیل» کلی را دست‌کم 1 واحد کاهش می‌دهد و این پتانسیل از مقداری بیش از مضربی ثابت از n آغاز نمی‌شود. پس دورهای سنگین تنها O(n) بار قابل برداشتن‌اند.
- تعداد رأس‌ها. وقتی دیگر دور سنگینی نماند، گراف «سبک» است — و قضیهٔ اصلی جدید نشان می‌دهد که یک گراف سبک با درجه‌های بزرگ باید ناحیه‌ای چگال و تقریباً بسته داشته باشد. این ناحیه به تعدادی دور و یال متناسب با اندازه‌اش تقسیم می‌شود و پس از آن دست‌کم یک‌پنجاهم رأس‌هایش با حداکثر دو یال باقی می‌مانند و برای همیشه کنار می‌روند. از آنجا که هر رأس تنها یک بار می‌تواند کنار رود، این بخش نیز O(n) هزینه دارد.
در بخش‌های چگال گراف، تکه‌های مسیرها با مسیرهای اتصالی که از «گسترنده‌ها» (expanders) می‌گذرند، در یک دور واحد بسته می‌شوند؛ یک رنگ‌آمیزی تصادفی مسیرهای اتصال یک دور را از هم جدا نگه می‌دارد. — Figure 3, Kim (2026), arXiv:2610.07840.
برای تقسیم این ناحیه‌های چگال، اثبات جعبه‌ابزار بوچیچ و مونتگومری از «گسترنده‌های» مقاوم — گراف‌هایی که در آن‌ها هر مجموعه از رأس‌ها همسایه‌های زیادی دارد — را گسترش می‌دهد و رأس‌ها را به‌طور تصادفی رنگ می‌کند تا مسیرهای اتصال یک دور هرگز با هم برخورد نکنند.
آنچه هنوز باز است
ثابت C بسیار بزرگ است و نویسنده تلاشی برای بهینه کردن آن نکرده است. یافتن بهترین ثابت — دست‌کم ۱٫۵ — همچنان باز است، همچنین صورت دقیق حدس هایوش و حدس مرتبطی از گالای دربارهٔ تقسیم گراف‌ها به مسیرها. ترفند وزن‌دهی تنها به وزن‌هایی نیاز دارد که مجموعشان همگرا باشد، و نویسنده پیشنهاد می‌کند که می‌تواند در دیگر مسائل تجزیه نیز به کار آید.
این یک پیش‌انتشار تک‌نویسنده است که هنوز داوری همتا نشده است.
تعارض منافع. نویسنده اعلام می‌کند که در پروراندن استدلال‌ها و آماده‌سازی متن و شکل‌ها به‌طور گسترده از ChatGPT (OpenAI) و Claude (Anthropic) استفاده کرده، همهٔ نتایج را راستی‌آزمایی کرده و مسئولیت کامل مقاله را می‌پذیرد. متنی که می‌خوانید نیز به دست Claude نوشته شده است.