Filtr seznamu úloh?

Zvolte požadované hodnoty úrovní a požadované štítky. V obsahu budou zobrazeny pouze úlohy mající jednu ze zvolených úrovní každé škály a alespoň jeden štítek. Pokud chcete filtrovat pouze podle některých škál nebo jen podle štítků, nechte ostatní skupiny prázdné.

Škály

Obtížnost

Štítky

Typ úlohy
«
«
«

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.

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze