KIKOMO CHA MITANDAO, SASA KIMETHIBITISHWA KWA KILA UKUBWA

Chukua nukta chache na uunganishe baadhi ya jozi zake kwa mistari. Wanahisabati huita hii grafu (graph): nukta ni vipeo (vertices) vyake, mistari ni kingo (edges) zake, na umbali kati ya vipeo viwili ni idadi ndogo kabisa ya kingo zinazohitajika kutembea kutoka kimoja hadi kingine. Sasa ongeza sheria mbili. Kila jozi ya vipeo lazima iwe katika umbali wa 2 au chini — vimeunganishwa moja kwa moja, au kupitia jirani wa pamoja. Na hakuna ukingo unaoweza kuwa wa ziada: futa ukingo wowote mmoja, na jozi fulani huishia kuwa zaidi ya hatua mbili mbali. Grafu kama hiyo huitwa grafu muhimu ya kipenyo-2 (diameter-2-critical). Inaweza kuwa na kingo ngapi?

Dari ya Mantel, na kisio la kijasiri zaidi

Mwaka 1907, Mantel alithibitisha kwamba grafu yenye vipeo n isiyo na pembetatu — yaani isiyo na vipeo vitatu vyote vilivyounganishwa kila kimoja na vingine — ina kingo ⌊n²/4⌋ kwa upeo: n ikiwa imezidishwa kwa yenyewe na kugawanywa kwa nne, ikishushwa hadi namba kamili. Ni grafu moja tu inayofikia dari hiyo, grafu kamili ya pande mbili iliyosawazishwa (balanced complete bipartite graph): makundi mawili yaliyo sawa kwa ukubwa kadiri inavyowezekana, kila kipeo cha kundi moja kikiunganishwa na kila kipeo cha kundi lingine, bila ukingo wowote ndani ya kundi.

Kila grafu isiyo na pembetatu ambayo haiwezi kupokea ukingo mmoja zaidi bila kuunda pembetatu ni grafu muhimu ya kipenyo-2. Kinyume chake si kweli: baadhi ya grafu muhimu za kipenyo-2 zina pembetatu.

Grafu muhimu ya kipenyo-2 yenye vipeo 7 na kingo 9, inayojumuisha pembetatu v1v3v5. Kufuta v1v3 huharibu njia pekee ya hatua mbili kati ya v2 na v3; kufuta ukingo ulio nje ya pembetatu huziacha ncha zake bila njia yoyote ya hatua mbili. — Kielelezo 1, Das & Fox (2026), arXiv:2610.39032.

Kisio lilikuwa kwamba pembetatu hazileti faida yoyote: grafu muhimu ya kipenyo-2 yenye vipeo n bado ina kingo ⌊n²/4⌋ kwa upeo, na grafu kamili ya pande mbili iliyosawazishwa bado ndiyo pekee inayoifikia dari hiyo. Nadharia-thibitisho ya Mantel ingefuata kama kisa maalum. Kwa vipeo 7 vya kielelezo, dari ni kingo 12.

Mnara wa 2

Kwa mujibu wa Erdős, kama ilivyoripotiwa na Zoltán Füredi, swali hili linarudi kwenye kazi ya Ore katika miaka ya 1960. Ján Plesník alieleza kikomo hicho cha kingo kama dhana (conjecture) mwaka 1975; Murty na Simon waliipendekeza kila mmoja kivyake na kuongeza kwamba grafu kamili ya pande mbili iliyosawazishwa ndiyo kisa pekee cha mwisho kabisa — hivyo jina dhana ya Murty–Simon. Katika miaka ya 1970 na 1980, vikomo vya umbo c·n² vilishuka polepole, c ikikaribia zaidi na zaidi 1/4.

Mwaka 1992, Füredi aliithibitisha dhana hiyo kwa kila n kubwa vya kutosha, kwa mbinu za utaratibu (regularity methods) — zana zinazotokana na lema ya utaratibu ya Szemerédi. Gharama ilikuwa ukubwa wa kuanzia: n ilipaswa kuwa angalau mnara wa 2 wenye kimo cha takriban 10¹⁴, yaani 2 kwa kipeo 2 kwa kipeo 2…, ikikokotolewa kuanzia juu kwenda chini — kila 2 ikipandishwa kwa kipeo cha vyote vilivyo juu yake — zikiwa na takriban 2 zipatazo 10¹⁴ katika rundo hilo. Chini ya ukubwa huo, ni familia maalum tu za grafu zilizokuwa zimeshughulikiwa.

Kingo dhidi ya kingo zinazokosekana

Uthibitisho mpya, wa Sanjana Das na Jacob Fox wa Idara ya Hisabati ya Stanford University, unafanya kazi kwa kila n kuanzia 3 na kuendelea. Unatumia upatanisho wa juu kabisa (maximal matching): seti ya kingo ambazo hakuna mbili kati yake zinazoshiriki kipeo, na ambayo hakuna ukingo mwingine unaoweza kuongezwa bila mbili kati yake kukutana. Upatanisho kwenye vipeo n hushikilia kingo ⌊n/2⌋ kwa upeo.

Lema muhimu: katika grafu muhimu ya kipenyo-2, kwa upatanisho wa juu kabisa wowote, kingo zilizo nje ya upatanisho kamwe si nyingi zaidi ya zisizo-kingo (non-edges) — jozi za vipeo ambazo hazijaunganishwa. Kilichobaki ni hesabu. Mara mbili ya idadi ya kingo ni kwa upeo idadi ya jozi pamoja na ukubwa wa upatanisho. Kwa vipeo 10: jozi 45 pamoja na kingo 5 za upatanisho kwa upeo hufanya 50, hivyo kingo 25 kwa upeo. Kwa kila n, jumla hiyo inakuwa sawasawa mara mbili ya dari ya Mantel.

Lema yenyewe ni uhasibu wa makini. Kisicho-ukingo ni muhimu (critical) ikiwa njia moja tu ya hatua mbili inaunganisha ncha zake, kama ilivyo kwa zisizo-kingo zote kumi na mbili za Kielelezo 1. Waandishi huunganisha kila kisicho-ukingo muhimu na kingo mbili za njia yake na kugawanya mtandao unaotokea kuwa vipande vilivyounganika. Kipande hushikilia kwa upeo ukingo mmoja zaidi kuliko zisizo-kingo muhimu, na kila kipande chenye ziada hiyo lazima kilipiwe na kisicho-ukingo kisicho muhimu. Ili kuvipata, waandishi hutumia njia za kutoka kwa kubadilishana (switch exits): chukua ukingo au kisicho-ukingo muhimu cha kipande na ubadilishe moja ya ncha zake kwa mwenzi wa ncha hiyo katika upatanisho. Kila kisicho-ukingo kisicho muhimu hudaiwa mara mbili kwa upeo, kila kipande chenye ziada hufanya madai mawili angalau, na hesabu hufungika.

Nani aligundua nini

«Uthibitisho huu ulipatikana kwa sehemu kubwa na AI, hasa GPT-5.6 Sol mnamo Agosti 11, 2026», waandishi wanaandika katika taarifa fupi kuhusu AI. Modeli ilipata uthibitisho kamili wa kikomo ⌊n²/4⌋, ambao waliurahisisha. Kwa idadi shufwa ya vipeo, pia ilithibitisha kwamba grafu kamili ya pande mbili iliyosawazishwa ndiyo kisa pekee cha mwisho kabisa, ikitegemea ukweli uliothibitishwa na Sumner kuhusu grafu ambazo kila upatanisho wa juu kabisa ndani yake ni kamili (perfect), unaofunika kila kipeo.

Kwa idadi witiri ya vipeo, hakuna upatanisho ulio kamili, na grafu nyingi zina kila upatanisho wa juu kabisa ukikosa kipeo kimoja hasa: hoja ya modeli haikuweza kurekebishwa. Waandishi walipata uthibitisho tofauti wa kisa cha usawa, halali kwa kila n, na waliandika makala wenyewe; upitiaji wa mwisho kupitia GPT-6 Astra ulileta «marekebisho machache madogo». Makala ni chapisho la awali (preprint), ambalo bado halijapitiwa na wataalamu wenzao, na halitaji toleo lolote la hoja lililokaguliwa na kompyuta.

Kurudi 1907

Ikiwa grafu inalingana na dari, ukosefu-usawa muhimu huwa usawa kwa upatanisho wa juu kabisa wowote. Kwa kuchagua upatanisho kwa werevu, waandishi wanaonyesha kwamba grafu kama hiyo ama ni nyota (star) — kipeo kimoja kilichounganishwa na vingine vyote, na hakuna kingine — au haina kisicho-ukingo muhimu chochote. Katika grafu muhimu ya kipenyo-2, kila ukingo wa pembetatu uko kwenye njia fulani muhimu, kwa hiyo kutokuwa na kisicho-ukingo muhimu kunamaanisha kutokuwa na pembetatu; nyota nayo haina pembetatu. Kwa hiyo grafu inayolingana na dari haina pembetatu, na hatua ya mwisho ni nadharia-thibitisho ambayo dhana hiyo ilikusudia kuiimarisha: tokeo la Mantel la 1907, linaloiacha grafu kamili ya pande mbili iliyosawazishwa peke yake kwenye dari.