Doplňky rovinných grafů
Úloha číslo: 4114
Ukažte, že doplněk rovinného grafu s 11 vrcholy nemůže být rovinný, a najděte příklad co největšího rovinného grafu, jehož doplněk je rovinný.
Řešení
Na 11 vrcholech je 55 hran, tedy buď \(G\) nebo \(\overline G\) by musel mít alespoň 28 hran.
Rovinné grafy na 11 vrcholech ale mají nejvýše \(3{\cdot}11-6\) hran, tedy graf s 28 hranami na 11 vrcholech nemůže být rovinný.
Příklad rovinného grafu na osmi vrcholech, jehož doplněk je rovinný, je uveden na obrázku (pozice vrcholů jsou nezměněny).
Všimněte si, že doplněk je dokonce izomorfní originálu.
Pozn.: Na devíti vrcholech není žádný rovinný graf, který by měl rovinný doplněk. Vizte článek autoru Battle, Harary, Kodama z roku 1962: http://www.ams.org/journals/bull/
1962-68-06/S0002-9904-1962-10850-7/S0002-9904-1962-10850-7.pdf
