Lovashin Perfect Graph -lause [1] [2] sanoo, että suuntaamaton graafi on täydellinen silloin ja vain, jos sen komplementti on myös täydellinen. Tämä väite ilmaistiin Bergen olettamuksena [3] [4] ja väitettä kutsutaan joskus heikon täydellisen graafin lauseeksi, jotta sitä ei sekoitettaisi tiukkaan täydellisen graafin lauseeseen [5] , joka kuvaa täydellisiä graafia niiden mukaan. kielletyt luodut alagraafit .
Täydellinen graafi on suuntaamaton graafi, jonka missä tahansa generoidussa aligraafissa sen suurimman klikkin koko on yhtä suuri kuin osagraafin väritysvärien vähimmäismäärä . Täydelliset kaaviot sisältävät monia tärkeitä kaavioluokkia, mukaan lukien kaksiosaiset kaaviot , sointukuvaajat ja vertailukaaviot .
Graafin komplementilla on reuna kahden kärjen välillä silloin ja vain, jos alkuperäisessä graafissa ei ole sellaista reunaa. Siten alkuperäisen graafin klikkauksesta tulee itsenäinen joukko komplementissa ja alkuperäisen graafin värityksestä tulee komplementin klikkipeite .
Täydellinen kuvaajalause sanoo:
Täydellisen kaavion komplementti on täydellinen.Vastaava muotoilu: Täydellisessä kaaviossa suurimman riippumattoman joukon koko on yhtä suuri kuin klikkien vähimmäismäärä klikkipeitteessä.
Olkoon G kuvaajasykli , jonka pituus on pariton yli kolme (ns. "pariton reikä"). Tällöin jokainen G :n väritys vaatii vähintään kolme väriä, mutta kolmioita ei ole, joten kaavio ei ole täydellinen. Täydellisen graafin lauseen mukaan graafin G komplementin ("pariton vastareikä") täytyy siksi olla myös epätäydellinen. Jos graafi G on viiden kärjen sykli, se on isomorfinen komplementtinsa kanssa, mutta tämä ei pidä paikkaansa pidempien syklien kohdalla. Ei-triviaali tehtävä on laskea klikkiluku ja kromaattinen luku parittomassa antireiässä ja parittisessa reiässä. Kuten tiukka täydellisen graafin lause sanoo , parittomat reiät ja parittomat antireiät osoittautuvat täydellisten graafien vähimmäiskielletyiksi indusoiduiksi osagraafiksi .
Ei-triviaalissa kaksiosaisessa graafissa optimaalinen värien määrä on (määritelmän mukaan) kaksi, ja (koska kaksiosaiset graafit eivät sisällä kolmioita ) suurin klikkin koko on myös kaksi. Siten mikä tahansa kaksiosaisen graafin luotu osagraafi pysyy kaksiosaisena. Näin ollen kaksiosaiset graafit ovat täydellisiä. Kaksiosaisissa graafeissa, joissa on n kärkeä, suurin klikkipeitto on suurimman sovituksen muodossa , sekä lisäklikki jokaiselle peittämättömälle pisteelle, jonka koko on n − M , missä M on sovituksen elementtien lukumäärä. Tässä tapauksessa täydellinen graafilause tarkoittaa Königin lausetta, jonka mukaan suurimman riippumattoman joukon koko kaksiosaisessa graafissa kaksiosaisessa graafissa on myös n − M [6] , mikä oli tärkein sysäys Bergen muotoilulle täydellisten graafien teoria.
Mirskyn lause , joka kuvaa posetin korkeuttajakautumisena antiketjuihin , voidaan muotoilla posetin vertailukäyrän täydellisyydeksi , ja Dilworthin lauseet , jotka kuvaavat posetin leveyttä osioiden ketjuihin, voidaan muotoilla näiden kaavioiden komplementtien täydellisyydeksi. Täydellistä kuvaajalausetta voidaan siis käyttää todistamaan Dilworthin lause Mirskyn lauseen (yksinkertaisemman) todistuksen perusteella tai päinvastoin [7] .
Todistaakseen lauseen täydellisistä graafista Lovash käytti operaatiota, jossa graafin kärkipisteet korvattiin klikkeillä. Berge tiesi jo, että jos graafi on täydellinen, myös tällaisella korvauksella saatu graafi on täydellinen [8] . Mikä tahansa tällainen korvausprosessi voidaan jakaa toistuviin huippupisteiden kopiointivaiheisiin. Jos monistettu kärki kuuluu graafin suurimpaan klikkiin, se lisää klikkin lukua ja kromaattista lukua yhdellä. Jos toisaalta monistettu kärki ei kuulu suurimpaan klikkiin, muodosta graafi H poistamalla graafin optimaalisesta värityksestä samanväriset kärjet kuin monistettu (mutta ei itse monistettu kärki). Poistettavat kärjet sisältyvät kaikkiin suuriin klikeihin, joten H :lla on klikkien lukumäärä ja kromaattinen numero yksi pienempi kuin alkuperäisessä graafissa. Poistetut pisteet ja uudet kopiot monistetuista kärjeistä voidaan lisätä yhteen väriluokkaan, mikä osoittaa, että monistusvaihe ei muuta kromaattista numeroa. Samat argumentit osoittavat, että tuplaus pitää klikkien määrän yhtä suurena kuin kromaattinen luku jokaisessa generoidussa graafin aligraafissa, joten jokainen tuplausvaihe pitää graafin täydellisenä [9] .
Täydellisellä graafilla G Lovash generoi graafin G * korvaamalla jokaisen kärjen v klikillä , jolla on tv - pisteet, missä t v on erillisten maksimierillisten joukkojen lukumäärä G :ssä, joka sisältää v : n . Jokaiseen G :n eri maksimaaliseen riippumattomaan joukkoon voidaan liittää maksimaalinen riippumaton joukko G *:ssa siten, että G*:n riippumattomat joukot ovat kaikki disjunkteja ja G *:n kukin kärkipiste esiintyy ainoassa valitussa joukossa. Toisin sanoen G *:lla on väritys, jossa jokainen väriluokka on maksimaalinen itsenäinen joukko. Tämä väritys on välttämättä optimaalinen G *:n väritys. Koska G on täydellinen, niin on myös G *, ja sitten sillä on maksimaalinen klikki K *, jonka koko on yhtä suuri kuin tämän värityksen värien lukumäärä, joka on yhtä suuri kuin G :n erilaisten maksimiriippumattomien joukkojen lukumäärä . Välttämättä K * sisältää erilaisen esityksen jokaiselle näistä maksimijoukoista. Vastaava G :n kärkijoukko K ( pisteet, joiden G *:n laajennetut klikkit leikkaavat K *) on G :n klikki, jolla on ominaisuus, että se leikkaa minkä tahansa suurimman riippumattoman joukon G :ssä . Siten G :stä poistamalla K muodostetun graafin klikkin peittoluku ei ole suurempi kuin G :n klikkiluku ilman yhtä, ja riippumattomuusluku on vähintään yhden pienempi kuin G :n riippumattomuusluku . Tulos seuraa tämän luvun induktiosta [10]
Chudnovskajan, Robertsonin, Seymourin ja Thomasin [11] vahva lause täydellisistä graafeista sanoo, että graafi on täydellinen silloin ja vain, jos mikään generoiduista osagraafista ei ole parittoman pituinen sykli, joka on suurempi tai yhtä suuri kuin viisi, eikä se myöskään ole sellaisen syklin komplementti . Koska tällainen kuvaus on epäherkkä kuvaajakomplementtioperaatiolle, seuraa heti heikko täydellisen graafin lause.
Cameron, Edmonds ja Lovasz [12] osoittivat, että jos täydellisen graafin reunat jaetaan kolmeen osagraafiin siten, että mitkä tahansa kolme kärkeä muodostavat yhdistetyn graafin yhdessä kolmesta osagraafista, ja jos kaksi aligraafista on täydellisiä , silloin myös kolmas osagraafi on täydellinen. Täydellinen kuvaajalause on tämän tuloksen erikoistapaus, kun yksi kolmesta graafista on tyhjä graafi .