A Lovash Perfect Graph Theorem [1] [2] kimondja, hogy egy irányítatlan gráf akkor és csak akkor tökéletes , ha a komplementere is tökéletes. Ezt az állítást Berge sejtése [3] [4] formájában fejezte ki, és az állítást néha gyenge tökéletes gráftételnek is nevezik, nehogy összetévessze a szigorú tökéletes gráftétellel [5] , amely a tökéletes gráfokat úgy írja le. tiltott generált részgráfok .
A tökéletes gráf egy irányítatlan gráf, amelynek bármely generált részgráfjában a legnagyobb klikkjének mérete megegyezik az algráf színező színeinek minimális számával. A tökéletes gráfok számos fontos grafikonosztályt foglalnak magukban, beleértve a kétrészes gráfokat , akkordgráfokat és összehasonlíthatósági gráfokat .
Egy gráf komplementerének akkor és csak akkor van éle két csúcs között, ha az eredeti gráfnak nincs ilyen éle. Így az eredeti gráfban lévő klikk független halmazzá válik a komplementben, az eredeti gráf színe pedig a komplementer klikkborítójává válik .
A tökéletes gráftétel kimondja:
A tökéletes gráf komplementere tökéletes.Egyenértékű megfogalmazás: Tökéletes gráfban a legnagyobb független halmaz mérete megegyezik a klikk fedőben lévő klikkek minimális számával.
Legyen G egy háromnál nagyobb páratlan hosszúságú gráfciklus (az úgynevezett „páratlan lyuk”). Ekkor G minden színezéséhez legalább három szín szükséges, de nincs háromszög, így a grafikon nem tökéletes. A tökéletes gráftétel szerint tehát a G gráf komplementerének (a "páratlan antilyuknak") is tökéletlennek kell lennie. Ha egy G gráf öt csúcsból álló ciklus, akkor izomorf a komplementerével , de ez nem igaz hosszabb ciklusokra. Nem triviális feladat a klikkszám és a kromatikus szám kiszámítása egy páratlan antilyukban és egy páratlan lyukban. Ahogy a szigorú tökéletes gráf-tétel kimondja , a páratlan lyukak és a páratlan antilyukak a tökéletes gráfok minimálisan tiltott indukált részgráfjainak bizonyulnak.
Egy nem triviális bipartit gráfban a színek optimális száma (definíció szerint) kettő, és (mivel a bipartit gráfok nem tartalmaznak háromszögeket ) a legnagyobb klikkméret is kettő. Így egy kétrészes gráf bármely generált részgráfja bipartit marad. Így a bipartit gráfok tökéletesek. Az n csúcsú kétrészes gráfokban a legnagyobb klikk lefedettség a legnagyobb illesztés formájában jelentkezik , valamint egy további klikk minden egyes n − M méretű fedetlen csúcsra , ahol M az illesztésben lévő elemek száma. Ebben az esetben a tökéletes gráftétel König tételét vonja maga után , miszerint a maximális független halmaz mérete egy bipartit gráfban egy bipartit gráfban is n − M [6] , ez az eredmény volt a fő ösztönzés Berge által a tökéletes gráfok elmélete.
Mirsky tétele , amely leírja a pozet magasságát az antiláncokra való felosztás szempontjából, megfogalmazható egy póz összehasonlíthatósági gráfjának tökéletesítéseként , és Dilworth tételei , amelyek a póz szélességét írják le a láncokra való felosztás szempontjából, e gráfok komplementereinek tökéletességeként fogalmazható meg. Így a tökéletes gráftétel felhasználható Dilworth tételének bizonyítására, Mirsky tételének (egyszerűbb) bizonyítására támaszkodva, vagy fordítva [7] .
A tökéletes gráfokra vonatkozó tétel bizonyítására Lovash azt a műveletet használta, hogy a gráf csúcsait klikkekkel helyettesítette. Berge már tudta, hogy ha a gráf tökéletes, akkor az ilyen helyettesítéssel kapott gráf is tökéletes lesz [8] . Bármely ilyen cserefolyamat ismételt csúcsduplikációs lépésekre bontható. Ha a duplikált csúcs a gráf legnagyobb klikkjéhez tartozik, akkor a klikkszámot és a kromatikus számot eggyel növeli. Ha viszont a duplikált csúcs nem tartozik a legnagyobb klikkhez, akkor a H gráfot úgy alakítsuk ki, hogy a megkettőzött csúcsokkal azonos színű csúcsokat (de magát a duplikált csúcsot nem) eltávolítjuk a gráf optimális színezéséből. Az eltávolítandó csúcsok minden legnagyobb klikkben benne vannak, így H -nak a klikkek száma és a kromatikus száma eggyel kevesebb, mint az eredeti gráfban. Az eltávolított csúcsok és a duplikált csúcsok új másolatai egyetlen színosztályhoz adhatók, ami azt mutatja, hogy a sokszorosítási lépés nem változtatja meg a kromatikus számot. Ugyanezek az érvek azt mutatják, hogy a duplázás megtartja a klikkek számát az adott gráf minden generált részgráfjában a kromatikus számmal, így a duplázás minden lépése tökéletesnek tartja a gráfot [9] .
Adott egy tökéletes G gráf , Lovash egy G * gráfot generál úgy, hogy minden v csúcsot egy t v csúcsokkal rendelkező klikkre cserél , ahol t v a G -ben lévő, v -t tartalmazó , egymástól elkülönülő maximálisan eltérő halmazok száma . Minden G -beli maximális független halmazhoz társítható egy maximális független halmaz G *-ban oly módon, hogy a G *-beli független halmazok mind diszjunktak, és G * minden csúcsa az egyetlen kiválasztott halmazban jelenik meg. Vagyis a G *-nak van egy színezése, amelyben minden színosztály egy maximális független halmaz. Ez a színezés szükségszerűen a G * optimális színezése lesz . Mivel G tökéletes, így G * is, és akkor van egy maximális K * klikkje, amelynek mérete megegyezik a színezésben lévő színek számával, ami egyenlő a G -ben lévő különböző maximális független halmazok számával . Szükségszerűen a K * minden egyes maximális halmazhoz más reprezentációt tartalmaz. A G -beli csúcsok megfelelő K halmaza (azok a csúcsok, amelyeknek a kiterjesztett klikkjei G *-ban metszik K *-t) G - beli klikk, azzal a tulajdonsággal, hogy metszi G -ben bármely maximális független halmazt . Így a G -ből K eltávolításával kialakított gráf klikkfedőszáma nem nagyobb, mint az egy nélküli G klikkszáma , a függetlenségi szám pedig legalább eggyel kisebb, mint G függetlenségi száma . Az eredmény ezen a számon való indukcióból következik [10]
Chudnovskaya, Robertson, Seymour és Thomas erős tétele a tökéletes gráfokról [11] kimondja, hogy egy gráf akkor és csak akkor tökéletes, ha a generált részgráfok egyike sem olyan páratlan hosszúságú ciklus, amely nagyobb vagy egyenlő öttel, és nem is egy ilyen ciklus komplementere . Mivel egy ilyen leírás érzéketlen a gráfkomplementer műveletre, azonnal következik a gyenge tökéletes gráf tétel.
Cameron, Edmonds és Lovasz [12] bebizonyították, hogy ha egy teljes gráf éleit három részgráfra osztjuk úgy, hogy bármely három csúcs összefüggő gráfot generál a három részgráf egyikében, és ha kettő részgráf tökéletes. , akkor a harmadik részgráf is tökéletes. A tökéletes gráftétel ennek az eredménynek egy speciális esete, amikor a három gráf egyike az üres gráf .