Santa Claus — 2021-11-25 17:38 (405 days ago) — edit — reply
Pomocné tvrzení:
$\forall \text{grafy } G, H: G \cong H \iff \overline{G} \cong \overline{H}$
Důkaz:
Intuitivně: Graf je charakterizován vrcholy a hranami stejně jako vrcholy a nehranami.
Formálně: Pokud existuje přejmenovaní, které zachovává hrany (isomorfismus), zachovává toto přejmenování i nehrany. Kdyby byla někde nehrana, kde být nemá, byla by tam hrana, která tam být nemá, takže by přejmenování nezachovávalo ani hrany - spor.
Důkaz věty:
Nejdříve si uvědomme, že pro lichá $n$ tato věta platí, protože neexistují žádné $(n-2)$-regulární grafy, neboť součet stupňů by potom byl lichý:
pro lichá $n$ vyjádřeme $n = 2p + 1$
Pak
$\sum_{v\in G} \deg(v) = n \cdot (n-2) = (2p + 1) \cdot (2p + 1 - 2) = 4p^2 - 1 = 2(2p^2) - 1$
opět liché číslo.
Pro sudé grafy se podívejme na jejich doplňky: jestliže v původním grafu měl každý vrchol $v$ stupeň $n-2$, sousedil ze zbývajících $n-1$ vrcholů s každým kromě jednoho. V doplňku tedy bude sousedit právě s jedním vrcholem $u$. $u$ ale bude sousedit také právě s jedním vrcholem, a protože už sousedí s $v$, nemá jiného souseda a dvojice $u,v$ tvoří komponentu souvislosti.
Doplněk takto definovaných grafů bude složen s komponent tvořených z dvou vrcholů. Nyní i vidíme, proč takový graf nelze zkonstruovat na lichém počtu vrcholů. Také je vidět, že každý takové graf je isomorfní s každým jiným, protože v rámci přejmenovaní stačí přejmenovat komponenty. A protože jsou doplňky isomorfní, jsou i původní grafy isomorfní.