Kombinatorika a grafy II - Hubička 30. 1. 2019

Vše co není uvedeno jinde
NeverNotBluu
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 4. 6. 2018 19:43
Typ studia: Informatika Bc.

Kombinatorika a grafy II - Hubička 30. 1. 2019

Příspěvek od NeverNotBluu »

1) Formulujte a dokažte Tutteovu větu.
2) Nechť G je 42-regulární graf se 123 vrcholy. Dokažte, že G má hranovou barevnost 43.

Řešení 2:
Kdyby měl barevnost 42, každá barva by z regularity musela tvořit hrany perfektního párování (snadné rozmyslet), které ale lichý graf nemůže mít. Z Vizingovy věty tedy musí mít barevnost 43.
Odpovědět

Zpět na „Ostatní“