Lovashova věta o dokonalém grafu [1] [2] uvádí, že neorientovaný graf je dokonalý právě tehdy, když je dokonalý i jeho doplněk . Toto tvrzení bylo vyjádřeno ve formě Bergeovy domněnky [3] [4] a tvrzení se někdy nazývá slabá věta o dokonalém grafu, aby nedošlo k záměně s přísnou větou o dokonalém grafu [5] , která popisuje dokonalé grafy jejich zakázané generované podgrafy .
Dokonalý graf je neorientovaný graf, v kterémkoli vygenerovaném podgrafu je velikost jeho největší kliky rovna minimálnímu počtu barev vybarvujících podgraf . Dokonalé grafy zahrnují mnoho důležitých tříd grafů, včetně bipartitních grafů , akordických grafů a grafů srovnatelnosti .
Doplněk grafu má hranu mezi dvěma vrcholy právě tehdy, když původní graf takovou hranu nemá. Tím se klika v původním grafu stává nezávislou množinou v doplňku a zbarvení původního grafu se stává krycím klikem doplňku.
Věta o dokonalém grafu říká:
Doplněk dokonalého grafu je dokonalý.Ekvivalentní formulace: V dokonalém grafu je velikost největší nezávislé množiny rovna minimálnímu počtu klik v krytu kliky.
Nechť G je graf-cyklus liché délky větší než tři (takzvaná „lichá díra“). Pak každé vybarvení G vyžaduje alespoň tři barvy, ale neexistují žádné trojúhelníky, takže graf není dokonalý. Podle věty o dokonalém grafu musí být tedy doplněk grafu G ("lichá antidíra") také nedokonalý. Pokud je graf G cyklem pěti vrcholů, je izomorfní ke svému doplňku , ale to neplatí pro delší cykly. Netriviálním úkolem je vypočítat klikové číslo a chromatické číslo v liché antidíře a liché díře. Jak tvrdí přísná věta o dokonalém grafu , liché díry a liché antidíry se ukazují jako minimální zakázané indukované podgrafy dokonalých grafů.
V netriviálním bipartitním grafu je optimální počet barev (podle definice) dvě a (protože bipartitní grafy neobsahují trojúhelníky ), největší velikost kliky je také dvě. Jakýkoli vygenerovaný podgraf bipartitního grafu tedy zůstává bipartitní. Bipartitní grafy jsou tedy dokonalé. V bipartitních grafech s n vrcholy má největší pokrytí kliky podobu největší shody , spolu s další klikou pro každý nepokrytý vrchol o velikosti n − M , kde M je počet prvků ve shodě. V tomto případě věta o dokonalém grafu implikuje Königovu větu , že velikost maximální nezávislé množiny v bipartitním grafu v bipartitním grafu je také n − M [6] , což byl výsledek, který byl hlavním impulsem pro Bergeovu formulaci teorie dokonalých grafů.
Mirského teorém , popisující výšku posetu z hlediska rozdělení na antiřetězce , lze formulovat jako dokonalost grafu srovnatelnosti posetu, a Dilworthovy věty , popisující šířku posetu z hlediska rozdělení do řetězců, lze formulovat jako dokonalost doplňků těchto grafů. Věta o dokonalém grafu tedy může být použita k prokázání Dilworthovy věty, spoléhat se na (jednodušší) důkaz Mirského věty nebo naopak [7] .
K prokázání teorému na dokonalých grafech použil Lovash operaci nahrazení vrcholů v grafu klikami. Berge již věděl, že pokud je graf dokonalý, bude dokonalý i graf získaný takovým nahrazením [8] . Každý takový proces nahrazení lze rozdělit na opakované kroky duplikace vrcholů. Pokud duplikovaný vrchol patří k největší klikě grafu, zvýší se počet kliků a chromatické číslo o jedna. Pokud naopak duplikovaný vrchol nepatří do největší kliky, vytvořte graf H odstraněním vrcholů stejné barvy jako duplikovaný (nikoli však samotný duplikovaný vrchol) z optimálního vybarvení grafu. Vrcholy, které mají být odstraněny, jsou zahrnuty ve všech největších klikách, takže H má počet kliků a chromatické číslo o jedna menší než v původním grafu. Odstraněné vrcholy a nové kopie duplikovaných vrcholů lze přidat do jedné třídy barev, což ukazuje, že krok duplikace nemění chromatické číslo. Stejné argumenty ukazují, že zdvojení udržuje počet kliků rovný chromatickému číslu v každém vygenerovaném podgrafu daného grafu, takže každý krok zdvojení udržuje graf dokonalý [9] .
Daný dokonalý graf G , Lovash generuje graf G * tím, že nahradí každý vrchol v klikou s vrcholy t v , kde t v je počet zřetelných maximálních odlišných množin v G obsahujících v . Ke každé z různých maximálních nezávislých množin v G lze přidružit maximální nezávislou množinu v G * takovým způsobem, že nezávislé množiny v G * jsou všechny disjunktní a každý vrchol G * se objeví v jediné zvolené množině. To znamená, že G * má zbarvení, ve kterém je každá třída barev maximální nezávislou množinou. Toto zbarvení bude nutně optimálním zbarvením G *. Protože G je dokonalé, je také G * a má pak maximální kliku K *, jejíž velikost je rovna počtu barev v tomto zbarvení, což je rovna počtu různých maximálních nezávislých množin v G . K * nutně obsahuje různé reprezentace pro každou z těchto maximálních množin. Odpovídající množina K vrcholů v G (vrcholy, jejichž rozšířené kliky v G * protínají K *) je klika v G s vlastností, že protíná jakoukoli maximální nezávislou množinu v G . Graf vytvořený z G odstraněním K má tedy krycí číslo kliky ne větší než číslo kliky G bez jedničky a číslo nezávislosti je alespoň o jednu menší než číslo nezávislosti G . Výsledek vyplývá z indukce na toto číslo [10]
Silná věta o dokonalých grafech od Chudnovské, Robertsona, Seymoura a Thomase [11] říká, že graf je dokonalý tehdy a jen tehdy, když žádný z vygenerovaných podgrafů není cyklus o liché délce větší nebo roven pěti, a také není doplněk takového cyklu . Protože takový popis je necitlivý na operaci grafového doplňku, okamžitě následuje slabá věta o dokonalém grafu.
Cameron, Edmonds a Lovasz [12] dokázali, že pokud jsou hrany úplného grafu rozděleny do tří podgrafů tak, že libovolné tři vrcholy generují souvislý graf v jednom ze tří podgrafů, a pokud jsou dva z podgrafů dokonalé , pak je třetí podgraf také perfektní. Věta o dokonalém grafu je speciální případ tohoto výsledku, kdy jeden ze tří grafů je prázdný graf .