Grafy na čtyřech vrcholech

Nalezněte všechny neizomorfní grafy na čtyřech vrcholech.

U každého z nich určete, kolik by měl izomorfních protějšků, pokud by množina vrcholů byla předepsána (např. \(\{u,v,w,x\}\)).

Nápověda
Postupujte systematicky, např. podle počtu hran.
Řešení
Grafy jsou na následujícím obrázku, grafy nad sebou jsou vzájemně komplementární, jen poslední \(P_4\) je doplňkem sebe sama.

Komplementární grafy mají stejně velké třídy izomorfismů, jejich velikost je uvedena.

Konkrétně:
- Prázdný graf je jen jeden (každá permutace vrcholů dává stejný graf).
- Grafů s jednou hranou je šest – dvojici (hranu) lze ze čtyřprvkové množiny vybrat \(\binom{4}{2}=6\) způsoby.
- Grafů izomorfních \(P_3\cup K_1\) je dvanáct – pro izolovaný vrchol jsou čtyři možnosti, pro střed \(P_3\) pak tři ze zbylých vrcholů.
- Párování jsou jen tři, jsou určené třemi volbami, jak zvolit souseda k \(u\).
- \(K_{1{,}3}\) jsou čtyři – tolik voleb je pro centrální vrchol.
- Cest je \(\frac{4!}{2}\) – každá permutace dá uspořádání vrcholů do posloupnosti, dvě posloupnosti dají stejný graf pokud jsou vzájemně symetrické.
Odpověď
Na čtyřech vrcholech lze nalézt celkem 64 různých grafů, ale z nich je jen 11 neizomorfních.