IYAKA GA HANYOYIN SADARWA, YANZU AN TABBATAR DA ITA GA KOWANE GIRMA
Ɗauki wasu ɗigo kaɗan ka haɗa wasu nau’i-nau’i daga cikinsu da layuka. Masana lissafi suna kiran wannan graph: ɗigon su ne vertex ɗinsa, layukan su ne edge ɗinsa, kuma nisa tsakanin vertex biyu shi ne mafi ƙarancin edge da ake buƙata don tafiya daga ɗaya zuwa ɗayan. Yanzu ka ƙara dokoki biyu. Kowane nau’in vertex dole ya kasance a nisa 2 a mafi yawa — an haɗa su kai tsaye, ko ta hanyar maƙwabci ɗaya da suke rabawa. Kuma babu wani edge da zai zama na ƙari: share kowane ɗaya, sai wani nau’i ya ƙare da nisa fiye da matakai biyu. Ana kiran irin wannan graph diameter-2-critical. Edge nawa zai iya kasancewa da su?
Rufin Mantel, da hasashe mafi ƙarfin hali
A 1907, Mantel ya tabbatar da cewa graph mai vertex n ba tare da alwatika ba — babu vertex uku da dukansu aka haɗa su da juna — yana da edge ⌊n²/4⌋ a mafi yawa: n murabba’i raba da huɗu, an tattara shi ƙasa zuwa cikakkiyar lamba. Graph ɗaya kawai ke kaiwa wannan rufi, cikakken graph mai ɓangarori biyu masu daidaito (balanced complete bipartite graph): rukuni biyu masu girma daidai gwargwadon yiwuwa, kowane vertex na ɗaya an haɗa shi da kowane vertex na ɗayan, babu edge a cikin rukuni.
Kowane graph mara alwatika da ba zai iya ɗaukar ƙarin edge ɗaya ba tare da samar da alwatika ba diameter-2-critical ne. Akasin haka ba gaskiya ba ne: wasu graph masu diameter-2-critical suna ɗauke da alwatika.
Graph mai diameter-2-critical mai vertex 7 da edge 9, da ke ɗauke da alwatikan v1v3v5. Share v1v3 yana lalata hanya ɗaya tilo ta matakai biyu tsakanin v2 da v3; share edge a wajen alwatikan yana barin ƙarshensa ba tare da hanyar matakai biyu ba. — Hoto na 1, Das & Fox (2026), arXiv:2610.39032.
Hasashen shi ne alwatika ba sa ƙara komai: graph mai diameter-2-critical mai vertex n har yanzu yana da edge ⌊n²/4⌋ a mafi yawa, kuma cikakken graph mai ɓangarori biyu masu daidaito har yanzu shi kaɗai ke kaiwa gare shi. Ka’idar Mantel za ta biyo baya a matsayin wani lamari na musamman. Ga vertex 7 na hoton, rufin edge 12 ne.
Hasumiyar 2
A cewar Erdős, kamar yadda Zoltán Füredi ya ruwaito, tambayar ta samo asali ne daga aikin Ore a shekarun 1960. Ján Plesník ya bayyana iyakar edge a matsayin hasashe a 1975; Murty da Simon sun gabatar da shi daban-daban kuma suka ƙara da cewa cikakken graph mai ɓangarori biyu masu daidaito shi kaɗai ne lamarin ƙarshe — saboda haka hasashen Murty–Simon. A shekarun 1970 da 1980, iyakoki na siffar c·n² sun riƙa saukowa a hankali, c yana ƙara kusantar 1/4.
A 1992, Füredi ya tabbatar da hasashen ga kowane n mai girma isasshe, da hanyoyin regularity (regularity methods) — kayan aiki da aka samo daga lemma ta regularity ta Szemerédi. Farashin shi ne girman farawa: n dole ya kasance aƙalla hasumiyar 2 mai tsawon kusan 10¹⁴, wato 2 zuwa ƙarfin 2 zuwa ƙarfin 2…, da ake lissafawa daga sama zuwa ƙasa — kowane 2 ana ɗaga shi zuwa ƙarfin duk abin da ke samansa — da kusan 2 guda 10¹⁴ a cikin tarin. Ƙasa da wannan girma, iyalai na musamman na graph ne kawai aka warware.
Edge da edge da suka ɓace
Sabuwar hujjar, ta Sanjana Das da Jacob Fox na Sashen Lissafi na Jami’ar Stanford, tana aiki ga kowane n daga 3 zuwa sama. Tana amfani da matching mafi girma (maximal matching): rukunin edge, babu biyu da ke raba vertex, wanda ba za a iya ƙara masa wani edge ba tare da biyu daga cikinsu sun haɗu ba. Matching a kan vertex n yana ɗauke da edge ⌊n/2⌋ a mafi yawa.
Babbar lemma: a cikin graph mai diameter-2-critical, ga kowane matching mafi girma, edge da ke wajen matching ɗin ba sa taɓa fin yawan waɗanda ba edge ba (non-edges) — nau’in vertex da ba a haɗa su ba. Sauran lissafi ne kawai. Ninki biyu na adadin edge bai wuce adadin nau’i-nau’i da girman matching ɗin ba. Da vertex 10: nau’i-nau’i 45 da edge na matching 5 a mafi yawa sun zama 50, don haka edge 25 a mafi yawa. Ga kowane n, wannan jimillar ta yi daidai da ninki biyu na rufin Mantel.
Lemma ɗin kanta lissafi ne mai kulawa. Wanda ba edge ba yana critical idan hanya ɗaya tilo ta matakai biyu ce ke haɗa ƙarshensa, kamar dukan waɗanda ba edge ba goma sha biyu na Hoto na 1. Marubutan suna haɗa kowane critical wanda ba edge ba da edge biyu na hanyarsa kuma suna raba sakamakon saƙar zuwa sassa masu haɗe. Sashe ɗaya yana ɗauke da edge fiye da critical waɗanda ba edge ba da ɗaya a mafi yawa, kuma kowane sashe mai wannan ragi dole a biya shi da wanda ba edge ba mara critical. Don samo su, marubutan suna amfani da fitar musanya (switch exits): ɗauki edge ko critical wanda ba edge ba na sashen kuma ka musanya ɗaya daga cikin ƙarshensa da abokin wannan ƙarshen a cikin matching. Ana ɗaukar kowane wanda ba edge ba mara critical sau biyu a mafi yawa, kowane sashe mai ragi yana yin ɗauka aƙalla biyu, kuma ƙirgar tana rufewa.
Wa ya samo me
“Wannan hujjar galibi AI ne ya samo ta, musamman GPT-5.6 Sol a ranar 11 ga Agusta, 2026,” marubutan sun rubuta a cikin wata gajeriyar sanarwa game da AI. Samfurin ya samo cikakkiyar hujjar iyakar ⌊n²/4⌋, wadda suka sauƙaƙa. Ga adadin vertex mai cika (even), ya kuma tabbatar da cewa cikakken graph mai ɓangarori biyu masu daidaito shi kaɗai ne lamarin ƙarshe, yana dogara ga wata hujja da Sumner ya tabbatar game da graph inda kowane matching mafi girma ke cikakke (perfect), yana rufe kowane vertex.
Da adadin vertex mara cika (odd), babu matching da ke cikakke, kuma graph da yawa suna da kowane matching mafi girma da ke barin vertex ɗaya daidai: ba za a iya daidaita hujjar samfurin ba. Marubutan sun samo wata hujja daban ta lamarin daidaito, mai aiki ga kowane n, kuma sun rubuta takardar da kansu; zagaye na ƙarshe ta hanyar GPT-6 Astra ya kawo “’yan ƙananan gyare-gyare”. Takardar preprint ce, ba a yi mata bitar takwarorin masana ba tukuna, kuma ba ta ambaci wata sigar hujjar da kwamfuta ta duba ba.
Komawa zuwa 1907
Idan graph ya kai rufin daidai, babban rashin daidaiton yana zama daidaito ga kowane matching mafi girma. Ta hanyar zaɓar matching da hikima, marubutan sun nuna cewa irin wannan graph ko dai tauraro (star) ne — vertex ɗaya da aka haɗa da dukan sauran, babu wani abu — ko kuma ba shi da critical wanda ba edge ba ko ɗaya. A cikin graph mai diameter-2-critical, kowane edge na alwatika yana kan wata critical hanya, don haka rashin critical wanda ba edge ba yana nufin rashin alwatika; tauraro ma ba shi da shi. Saboda haka graph da ya kai rufin daidai ba shi da alwatika, kuma mataki na ƙarshe shi ne ka’idar da hasashen ya nemi ƙarfafawa: sakamakon Mantel na 1907, wanda ke barin cikakken graph mai ɓangarori biyu masu daidaito shi kaɗai a rufin.