Matematické Fórum

Úkol: Ukažte, že neexistuje žádný asymetrický graf G s 1 < |V(G)| <= 5


Moje řešení:

G=2: Graf s dvěma vrcholy a jednou hranou nemůže být asymetrický, protože existuje bijektivní zobrazení, které mi vrchol 1 zobrazí na vrchol 2 a vrchol 2 zobrazí na vrchol 1. Graf není asymetrický ani v případě, že nemá hranu (má pouze dva vrcholy).

Můžeme vynechávat případy, kdy vrchol není spojen hranou s žádným jiným vrcholem, a to proto, že aby byl graf asymetrický musí platit automorfismus grafu. Na vrchol bez hrany se tedy nemůže zobrazit žádný s vrchol, ze kterého vychází nějaká hrana, může se na něj zobrazit pouze vrchol, ze kterého nevychází žádná hrana, ale v tom případě už zase není tento graf asymetrický.

G=3: na trojúhelníku je příkladem grafu kružnice, kružnice nemůže být asymetrický graf, protože existuje bijektivní zobrazení, které nezmění množinu hran.

G=4: Lze nalézt kružnici. (Rozdělit graf na dva grafy s G=2 také nelze a nelze to proto, že pak bychom dostali graf, který asymetrický není)

G=5: Lze také nalézt kružnici.

Mohl by se mi prosím někdo podívat na mé řešení a upozornit na případné chyby? Děkuju