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

<{ForumPost(poster="NeverNotBluu", timestamp=2019-01-31 14:38:04)}>
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.
<{/ForumPost}>