Počet hran nesouvislého grafu
Úloha číslo: 3618
Určete minimální a maximální počet hran v grafu na \(n\) vrcholech s \(c\) komponentami.
Řešení
Nejméně hran bude mít takový graf, jehož každá komponenta nebude obsahovat cyklus a bude tedy strom. Takový má \(n-c\) hran.
Nejvíce hran bude mít graf, kde každá komponenta bude úplný graf. Maxima se dosáhne tehdy, bude-li \(c-1\) komponent jednobodových a jedna na \(n-c-1\) vrcholech.
Odpověď
Graf s \(c\) komponentami msí mít alespoň \(n-c\) hran a nejvýše \(\binom{n-c+1}{2}\).