SEBUAH BATAS PADA JARINGAN, KINI TERBUKTI UNTUK SEGALA UKURAN

Ambil beberapa titik dan hubungkan beberapa pasang di antaranya dengan garis. Matematikawan menyebutnya graf: titik-titiknya adalah simpul, garis-garisnya adalah sisi, dan jarak antara dua simpul adalah jumlah sisi paling sedikit yang diperlukan untuk berjalan dari satu simpul ke simpul lainnya. Sekarang tambahkan dua aturan. Setiap pasang simpul harus berjarak paling jauh 2 — terhubung langsung, atau melalui tetangga bersama. Dan tidak boleh ada sisi yang berlebih: hapus satu sisi mana pun, dan ada pasangan yang akhirnya terpisah lebih dari dua langkah. Graf semacam itu disebut kritis-diameter-2 (diameter-2-critical). Berapa banyak sisi yang dapat dimilikinya?

Plafon Mantel, dan tebakan yang lebih berani

Pada 1907, Mantel membuktikan bahwa graf dengan n simpul tanpa segitiga — tanpa tiga simpul yang semuanya saling terhubung — memiliki paling banyak ⌊n²/4⌋ sisi: n dikuadratkan dibagi empat, dibulatkan ke bawah menjadi bilangan bulat. Hanya satu graf yang mencapai plafon itu, yaitu graf bipartit lengkap seimbang: dua kelompok yang ukurannya sebisa mungkin sama, setiap simpul di satu kelompok terhubung ke setiap simpul di kelompok lainnya, tanpa sisi di dalam satu kelompok.

Setiap graf tanpa segitiga yang tidak dapat menerima satu sisi lagi tanpa menciptakan segitiga adalah graf kritis-diameter-2. Kebalikannya tidak berlaku: beberapa graf kritis-diameter-2 memuat segitiga.

Sebuah graf kritis-diameter-2 dengan 7 simpul dan 9 sisi, yang memuat segitiga v1v3v5. Menghapus v1v3 menghancurkan satu-satunya rute dua langkah antara v2 dan v3; menghapus sisi di luar segitiga membuat kedua ujungnya tanpa rute dua langkah. — Gambar 1, Das & Fox (2026), arXiv:2610.39032.

Tebakannya adalah bahwa segitiga tidak memberi keuntungan apa pun: graf kritis-diameter-2 dengan n simpul tetap memiliki paling banyak ⌊n²/4⌋ sisi, dan graf bipartit lengkap seimbang tetap satu-satunya yang mencapainya. Teorema Mantel akan menyusul sebagai kasus khusus. Untuk 7 simpul pada gambar itu, plafonnya adalah 12 sisi.

Menara angka 2

Menurut Erdős, seperti dilaporkan oleh Zoltán Füredi, pertanyaan ini berasal dari karya Ore pada dekade 1960-an. Ján Plesník menyatakan batas sisi itu sebagai konjektur pada 1975; Murty dan Simon mengajukannya secara independen dan menambahkan bahwa graf bipartit lengkap seimbang adalah satu-satunya kasus ekstrem — karena itulah disebut konjektur Murty–Simon. Pada dekade 1970-an dan 1980-an, batas-batas berbentuk c·n² perlahan turun, dengan c yang makin mendekati 1/4.

Pada 1992, Füredi membuktikan konjektur itu untuk setiap n yang cukup besar, dengan metode keteraturan (regularity methods) — perangkat yang diturunkan dari lema keteraturan Szemerédi. Harganya adalah ukuran awal: n harus setidaknya sebesar menara angka 2 setinggi kira-kira 10¹⁴, yaitu 2 pangkat 2 pangkat 2…, yang dihitung dari atas ke bawah — setiap 2 dipangkatkan dengan seluruh susunan di atasnya — dengan sekitar 10¹⁴ angka dua dalam tumpukan itu. Di bawah ukuran tersebut, hanya keluarga-keluarga graf khusus yang sudah terselesaikan.

Sisi melawan sisi yang hilang

Bukti baru ini, karya Sanjana Das dan Jacob Fox dari Departemen Matematika Stanford University, berlaku untuk setiap n mulai dari 3. Bukti itu memakai sebuah pemasangan maksimal (maximal matching): himpunan sisi yang tidak ada dua di antaranya berbagi simpul, dan yang tidak dapat ditambahi sisi lain tanpa dua di antaranya bertemu. Pemasangan pada n simpul memuat paling banyak ⌊n/2⌋ sisi.

Lema kuncinya: dalam graf kritis-diameter-2, untuk pemasangan maksimal mana pun, sisi-sisi di luar pemasangan tidak pernah lebih banyak daripada non-sisi — pasangan-pasangan simpul yang tidak terhubung. Sisanya adalah aritmetika. Dua kali jumlah sisi paling banyak sama dengan jumlah pasangan ditambah ukuran pemasangan. Dengan 10 simpul: 45 pasangan ditambah paling banyak 5 sisi pemasangan menghasilkan 50, sehingga paling banyak 25 sisi. Untuk setiap n, jumlah itu tepat sama dengan dua kali plafon Mantel.

Lema itu sendiri adalah pembukuan yang cermat. Sebuah non-sisi disebut kritis jika hanya satu rute dua langkah yang menghubungkan kedua ujungnya, seperti pada kedua belas non-sisi di Gambar 1. Para penulis mengaitkan setiap non-sisi kritis dengan dua sisi rutenya dan membagi jejaring yang dihasilkan menjadi potongan-potongan yang terhubung. Sebuah potongan memuat paling banyak satu sisi lebih banyak daripada non-sisi kritisnya, dan setiap potongan yang memiliki kelebihan itu harus dibayar oleh sebuah non-sisi tak kritis. Untuk menemukannya, para penulis memakai jalan keluar tukar (switch exits): ambil sebuah sisi atau non-sisi kritis dari potongan itu dan tukar salah satu ujungnya dengan pasangan ujung tersebut dalam pemasangan. Setiap non-sisi tak kritis diklaim paling banyak dua kali, setiap potongan yang berlebih mengajukan setidaknya dua klaim, dan hitungannya pun tuntas.

Siapa menemukan apa

“Bukti ini sebagian besar ditemukan oleh AI, khususnya GPT-5.6 Sol pada 11 Agustus 2026,” tulis para penulis dalam pernyataan singkat tentang AI. Model itu menemukan bukti lengkap untuk batas ⌊n²/4⌋, yang kemudian mereka sederhanakan. Untuk jumlah simpul genap, model itu juga membuktikan bahwa graf bipartit lengkap seimbang adalah satu-satunya kasus ekstrem, dengan bersandar pada fakta yang dibuktikan Sumner tentang graf yang setiap pemasangan maksimalnya sempurna, yaitu mencakup setiap simpul.

Dengan jumlah simpul ganjil, tidak ada pemasangan yang sempurna, dan banyak graf yang setiap pemasangan maksimalnya melewatkan tepat satu simpul: argumen model itu tidak dapat disesuaikan. Para penulis menemukan bukti lain untuk kasus kesamaan, yang berlaku untuk setiap n, dan menulis makalahnya sendiri; satu pemeriksaan terakhir melalui GPT-6 Astra menghasilkan “beberapa suntingan kecil”. Makalah ini adalah pracetak, belum ditelaah sejawat, dan tidak menyebutkan versi argumen yang diperiksa komputer.

Kembali ke 1907

Jika sebuah graf menyamai plafon, ketaksamaan kuncinya menjadi kesamaan untuk setiap pemasangan maksimal. Dengan memilih pemasangan secara cerdik, para penulis menunjukkan bahwa graf semacam itu adalah sebuah bintang — satu simpul yang terhubung ke semua simpul lain, tanpa sisi lain — atau sama sekali tidak memiliki non-sisi kritis. Dalam graf kritis-diameter-2, setiap sisi segitiga terletak pada suatu rute kritis, sehingga tanpa non-sisi kritis berarti tanpa segitiga; bintang pun tidak memiliki segitiga. Karena itu, graf yang menyamai plafon tidak memiliki segitiga, dan langkah terakhirnya adalah teorema yang hendak diperkuat oleh konjektur itu: hasil Mantel tahun 1907, yang menyisakan graf bipartit lengkap seimbang sendirian di plafon.