Kombinatorika a grafy II - Hubička 30. 1. 2019
Napsal: 31. 1. 2019 14:38
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.
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.