Regulární graf
Úloha číslo: 3624
Ukažte, že pokud má \(2k\)-regulární graf sudý počet hran, tak buď \(k\) nebo \(|V_G|\) je sudé.
Řešení
Sečteme-li stupně, dostaneme dvojnásobek celkového počtu hran, tedy \(|E_G|=\frac{2k|V_G|}2=k|V_G|\).
Pokud by oba činitelé byla lichá čísla, dostali bychom lichý počet hran, což by bylo ve sporu s předpoklady.
