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