Lemma 4 ([Cut test]). Let P be a k -connected graph on at most n vertices, where k is a sufficiently large integer. Set s=10(n/k)(2n). There is a family of at most (n+1)^ s+1 matchings, each of size k/8 , with the following property. If …

For every set R of at most s vertices, put B_R=⋃_ v∈R N_P(v) . Whenever both B_R and its complement have size at least k/3 , fix a matching of size k/8 across this cut. Such a matching exists: otherwise the endpoints of a maximal smaller matching form a vertex cover of the crossing edges, of size less than k/4 . Both sides remain nonempty after their removal, contradicting k -connectivity. The number of possible sets R , and hence of matchings, is at most (n+1)^ s+1 . The neighborhood assumption ensures that P-U has more than k/32 vertices. If it fails the asserted connectivity, there are a set Z⊆V(P) U with |Z|<k/32 and nonempty anticomplete sides A,A' partitioning V(P)(U∪Z) . Every vertex of either side has more than k/3 neighbors in that same side, since it has at least k/2 neighbors outside U and loses fewer than k/32 to Z . In particular both sides have size at least k/3 . Make s independent uniform draws from A . For each vertex v∈A , the probability that none of the draws is an open neighbor of v is at most (-ks/(3n)) . The union bound over A is less than one by the choice of s . Thus the set R of drawn vertices, after repetitions are removed, satisfies A⊆B_R . Since A,A' are anticomplete, A'∩B_R=∅ . The matching fixed for this cut has every edge incident with U∪Z , for otherwise an edge would join A to A' . But U contains fewer than k/32 of its endpoints, and Z contains fewer than k/32 vertices. They cannot cover its k/8 disjoint edges. This contradiction proves the lemma.