Problem
COM-B2-M08-P013 After Deleting a Vertex
#13
★★★★☆ Level 4 of 5
In a bipartite graph with left part \(A\), \(|N(S)|\ge |S|+2\) for every nonempty \(S\subseteq A\). Prove that after deleting any two vertices of the right part, there is still a matching covering \(A\).
Any \(N(S)\) loses at most two vertices.
Delete two right-side vertices. For any nonempty \(S\subseteq A\), its neighbour set loses at most two vertices. Hence the new neighbour set size is at least \(|S|+2-2=|S|\).
Hall's condition remains true, so there is a matching covering the left part.
A strengthened robustness version of Hall.