Formulujte a dokažte Tutteovu větu.
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.