Задача
COM-B2-M08-P013 После удаления вершины
#13
★★★★☆ Уровень 4 из 5
В двудольном графе с левой долей \(A\) выполнено \(|N(S)|\ge |S|+2\) для любого непустого \(S\subseteq A\). Докажите, что после удаления любых двух вершин правой доли всё ещё есть паросочетание, покрывающее \(A\).
Любое \(N(S)\) потеряет не больше двух вершин.
Удалим две правые вершины. Для любого непустого \(S\subseteq A\) его множество соседей потеряет не больше двух вершин. Поэтому новый размер соседства не меньше \(|S|+2-2=|S|\).
Условие Холла сохраняется, значит, существует паросочетание, покрывающее левую долю.
Усиленная версия робастности Холла.