(posts visible to all students)
Martin Koutecký — 2021-11-16 11:01 (415 days ago) — reply
## 6. cvičení ### [Isomorfismus doplňků](https://matematika.reseneulohy.cz/3573/izomorfismus-doplnku) ### Samodoplňkové kružnice Všimneme si, že kružnice je (mimojiné) graf, jehož každý vrchol má stupeň 2. Zároveň v doplňku $C_n$ má každý vrchol stupeň $n-3$. Tedy aby doplněk byla kružnice, tak musí být $n-3 = 2$ a to platí jen pro $n=5$. ### Stupně 4 nebo 5. Označme $k$ počet vrcholů stupně $4$ a $\ell$ počet vrcholů stupně $5$. Pak musí platit $k+\ell = 14$ a zároveň z principu sudosti $4k + 5\ell = 2|E| = 60$ a z toho už se dá řešení vypočítat. ### [Indukovaný lichý cyklus](https://matematika.reseneulohy.cz/3579/indukovany-cyklus) ### [Doplněk bipartitního](https://matematika.reseneulohy.cz/3572/doplnek-bipartitniho-grafu) ### Různé stupně Máme-li $n$ vrcholů, maximální stupeň je $n-1$. Jediných $n$ různých přirozených čísel nanejvýš $n-1$ je $0, 1, 2, \dots, n-1$, tedy toto by musela být (setříděná) posloupnost stupňů v našem grafu. Ale pak vrchol se stupněm $n-1$ musí sousedit se všemi ostatními, ale zároveň nemůže sousedit s vrcholem stupně $0$, tedy takový (konečný) graf neexistuje, s výjimkou $n=1$. ### [Přesný počet automorfismů](https://matematika.reseneulohy.cz/3575/presny-pocet-automorfismu)