Bipartitní graf s velkými stupni
Úloha číslo: 3770
Nechť \(G\) je bipartitní graf s \(2n\) vrcholy takový, že každá z jeho částí má \(n\) vrcholů.
Varianta
Předpokládejme, že minimální stupeň v \(G\) je alespoň \(n/2\). Dokažte, že \(G\) obsahuje perfektní párování.
Varianta
Musí \(G\) obsahovat perfektní párování, kdyby minimální stupeň byl \(\lceil n/2\rceil-1\)?