Задача
COM-B2-M04-P009 Максимальное паросочетание по включению
#9
★★★☆☆ Уровень 3 из 5
В графе выбрано множество попарно не имеющих общих концов рёбер, к которому нельзя добавить ещё одно ребро. Докажите, что между двумя вершинами, не покрытыми выбранными рёбрами, нет ребра.
Если такие две вершины соединены, это ребро можно добавить.
Предположим, что непокрытые вершины \(x\) и \(y\) соединены ребром \(xy\). Так как обе вершины не покрыты, ребро \(xy\) не имеет общих концов ни с одним выбранным ребром.
Тогда \(xy\) можно добавить к выбранному множеству, и рёбра всё ещё будут попарно не иметь общих концов. Это противоречит условию, что добавить ребро нельзя. Значит, такого ребра нет.
Подготовка к теме паросочетаний: задача специально оставлена без теоремы Холла.