Задача
COM-B2-M08-P002 Покрыть левую долю
#2
★★☆☆☆ Уровень 2 из 5
В двудольном графе паросочетание покрывает все \(a\) вершин левой доли. Докажите, что правая доля содержит не меньше \(a\) вершин.
Разные левые вершины сопоставлены разным правым.
Рёбра паросочетания не имеют общих концов. Поэтому \(a\) покрытых левых вершин соединены с \(a\) различными вершинами правой доли. Значит, справа есть хотя бы \(a\) вершин.
Базовая необходимость для matching.