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\)?

Obtížnost: Středně těžká úloha
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze