РАЗБОР ЗАДАЧИ - ТЕОРЕМА 6.

Теорема 6 (Кенига). Наибольшее количество ребер в паросочетании двудольного графа G равно наименьшему количеству вершин в вершинном покрытии графа G (вершинное покрытие — это такое множество вершин, что каждое ребро содержит хотя бы одну из них).