Úkoly z diskrétní matematiky, 8. série

Veškerá tvrzení precizně zdůvodněte.

(8.1) Graf G nazveme k-regulární, pokud stupeň každého jeho vrcholu je roven k. (i) Je pravda, že každé dva (n − 1)-regulární grafy jsou izomorfní? 1 bod (ii) Je pravda, že každé dva (n − 2)-regulární grafy jsou izomorfní? 2 body

(8.2) Pro která n existuje graf G na n vrcholech, jehož stupně jsou všechny různé až na dva (které tedy mohou být stejné)? Pokud pro daný počet vrcholů n graf existuje, popište jeho konstrukci (či jinak dokažte jeho existenci), pokud neexistuje, dokažte. 4 body

(8.3) Rozhodněte, zda existuje nebo neexistuje nesouvislý graf, jehož doplněk je opět nesouvislý graf. To, co tvrdíte, pochopitelně dokažte. (Graf je souvislý, pokud v něm existuje cesta z každého vrcholu do každého.) 3 body

(8.4) Nechť G = (V, E) je graf. Bijekci f: V → V nazveme automorfismus, pokud platí {u, v} ∈ E ⇔ {f(u), f(v)} ∈ E. (Je to tedy izomorfismus grafu sama na sebe.) Graf, který ma pouze jeden automorfismus (všimněte si, že to bude identita) nazveme strnulý. Najděte příklad nějakého strnulého grafu na n > 1 vrcholech a dokažte to o něm. 3 body