Hustý graf
Úloha číslo: 3821
Nechť \(G\) je libovolný graf na \(2n\) vrcholech, jehož každý vrchol má stupeň alespoň \(n\). Dokažte, že \(G\) je hranově \(n\)-souvislý.
Řešení
Má-li se graf rozdělit odebráním hran na několik komponent, alespoň jedna z komponent bude mít nejvýše \(n\) vrcholů. Mezi \(k\) vrcholy vede nejvýše \(\binom{k}{2}\) hran. Součet stupňů je \(kn\), tedy z této komponenty vychází alespoň \(kn-2\binom{k}{2}=k(n-k+1)\) hran. Tato funkce je na intervalu \([1,n]\) konkávní, s minimy v krajních bodech, kdy je počet vycházejících hran alespoň \(n\).
Z uvedeného dostáváme, že každý hranový řez musí mít alespoň \(n\) hran.
