TEKA-TEKI GRAF DARI TAHUN 1960-AN AKHIRNYA TERJAWAB

Ambil beberapa titik dan hubungkan sebagian pasangannya dengan garis: matematikawan menyebutnya graf, titik-titiknya simpul, dan garis-garisnya sisi. Sebuah siklus adalah putaran tertutup yang melewati simpul-simpul berbeda lalu kembali ke titik awalnya. Pertanyaan yang wajar adalah apakah sisi-sisi sebuah graf bisa dipecah — dengan setiap sisi dipakai tepat sekali — menjadi siklus-siklus.

Jawabannya sudah lama diketahui, seperti diingatkan makalah ini: hal itu mungkin tepat ketika setiap simpul menyentuh sejumlah genap sisi. Graf seperti itu disebut graf Euler. Pertanyaan berikutnya adalah berapa banyak siklus yang dibutuhkan. Dan untuk graf yang tidak bisa dipecah hanya menjadi siklus, sisi tunggal juga diperbolehkan sebagai potongan.

Konjekturnya

Pada 1960-an, Erdős dan Gallai menduga bahwa sisi-sisi setiap graf dengan n simpul dapat dipecah menjadi sejumlah siklus dan sisi tunggal yang paling banyak sebanding dengan n — ditulis O(n). Erdős memasukkannya ke dalam beberapa kumpulan masalah terbukanya. Sebuah konjektur terkait dari Hajós menuntut paling banyak (n − 1)/2 siklus pada setiap graf Euler.

Linear adalah yang terbaik yang bisa diharapkan: Erdős menunjukkan bahwa sebagian graf membutuhkan sekitar 1,5 n potongan. Pertanyaannya adalah apakah suatu konstanta dikali n selalu cukup.

Lima puluh tahun batas yang merayap

Erdős dan Gallai sendiri memperhatikan sebuah metode sederhana: berulang kali cabut siklus terpanjang. Metode ini menghasilkan sekitar n log n potongan — dan, menurut makalah ini, itu tetap menjadi batas umum terbaik selama hampir lima puluh tahun. Belakangan, Conlon, Fox, dan Sudakov menurunkannya menjadi n log log n, lalu Bucić dan Montgomery menjadi n log* n, dengan log* n — berapa kali kita harus mengambil logaritma agar hasilnya kurang dari satu — tumbuh dengan sangat lambat hingga sulit dibayangkan. Pendekatan-pendekatan ini bekerja dalam beberapa putaran kerja, dan setiap putaran memakan sekitar n siklus, sehingga jumlah putaran kerja selalu ikut masuk ke hitungan akhir. Konjektur ini juga sudah dibuktikan untuk keluarga khusus, seperti graf acak.

Bobot yang membayar putaran

Jaehoon Kim, dari KAIST di Korea Selatan, kini membuktikan konjektur tersebut: ada sebuah konstanta tetap C sehingga setiap graf dengan n simpul dapat dipecah menjadi paling banyak Cn siklus dan sisi. Sebagai akibatnya, konjektur Hajós berlaku hingga faktor konstan.

Bukti ini meninggalkan cara bertahap. Satu prosedur tunggal mencabut siklus dan sisi satu per satu, dan totalnya dikendalikan oleh dua besaran yang masing-masing tetap di bawah suatu konstanta dikali n.

• Potensial berdasarkan derajat. Setiap simpul mendapat bobot yang mengecil seiring jumlah sisinya, kira-kira 1 / (derajat × log² derajat). Sebuah siklus disebut berat jika jumlah bobot simpul-simpulnya paling sedikit 1. Mencabut siklus berat menurunkan sebuah “potensial” keseluruhan paling sedikit sebesar 1, dan potensial itu bermula dari tidak lebih dari suatu konstanta dikali n. Jadi siklus berat hanya bisa dicabut O(n) kali.
• Jumlah simpul. Ketika tak ada lagi siklus berat, grafnya “ringan” — dan teorema baru yang utama menunjukkan bahwa graf ringan dengan derajat besar pasti memuat wilayah padat yang hampir tertutup. Wilayah itu dipecah menjadi sejumlah siklus dan sisi yang sebanding dengan ukurannya, setelah itu paling sedikit seperlima puluh simpulnya tinggal memiliki paling banyak dua sisi dan keluar untuk selamanya. Karena setiap simpul hanya bisa keluar sekali, bagian ini juga memakan O(n).

Di dalam bagian graf yang padat, potongan-potongan lintasan ditutup menjadi satu siklus oleh lintasan penghubung yang dirutekan melalui “ekspander”; pewarnaan acak menjaga agar lintasan penghubung dari satu siklus tetap terpisah. — Gambar 3, Kim (2026), arXiv:2610.07840.

Untuk memecah wilayah-wilayah padat itu, bukti ini memperluas perangkat Bucić dan Montgomery berupa “ekspander” (expander) yang tangguh — graf yang setiap himpunan simpulnya memiliki banyak tetangga — dan mewarnai simpul secara acak agar lintasan penghubung dari siklus yang sama tidak pernah bertabrakan.

Apa yang masih terbuka

Konstanta C sangat besar, dan penulis tidak berusaha mengoptimalkannya. Menemukan konstanta terbaik — paling sedikit 1,5 — masih menjadi masalah terbuka, begitu pula konjektur Hajós dalam bentuk eksaknya dan sebuah konjektur terkait dari Gallai tentang pemecahan graf menjadi lintasan. Trik pembobotan ini hanya membutuhkan bobot yang jumlahnya konvergen, dan penulis menyarankan bahwa trik ini dapat berguna dalam masalah dekomposisi lainnya.

Ini adalah pracetak dari satu penulis, yang belum diperiksa melalui telaah sejawat.

Konflik kepentingan. Penulis menyatakan bahwa ia banyak memakai ChatGPT (OpenAI) dan Claude (Anthropic) dalam mengembangkan argumen serta menyiapkan teks dan gambar, dan bahwa ia telah memverifikasi semua hasil serta bertanggung jawab penuh atas makalah ini. Teks yang sedang Anda baca juga ditulis oleh Claude.