Задача
COM-B2-M07-P014 Максимальное паросочетание и покрытие рёбер
#14
★★★★☆ Уровень 4 из 5
В графе выбрано паросочетание, максимальное по включению. Докажите, что множество всех концов выбранных рёбер пересекает каждое ребро графа.
Если есть ребро с двумя непокрытыми концами, его можно добавить.
Предположим, что существует ребро \(uv\), оба конца которого не являются концами выбранных рёбер. Тогда \(uv\) не пересекается ни с одним ребром паросочетания, поэтому его можно добавить. Это противоречит максимальности по включению.
Значит, каждое ребро имеет хотя бы один конец среди концов выбранных рёбер.
Подводит к vertex cover и теореме Кёнига без формального введения.