Prove
Lemma 7. Take at most q independent copies of the experiment . Let Z be any one…Theorem 2.2 ([Ordinary-chromatic connectivity extraction]). If k≥1 is an…Proposition
Build a binary decomposition of P , making all choices before sampling. A node is an induced subgraph. Stop at a node of order at most 2k , and also at a larger node which is k -connected. Otherwise choose a separator of size less than k , partition the vertices outside it into two nonempty anticomplete sides, and form two children by adding the separator to each side. There are O(n^2+1) nodes. To see this, give a node of order u>2k potential u-k . Each large child's potential is strictly smaller than its parent's, since the other exclusive side is nonempty. If both children are large, their potentials sum to at most their parent's: their orders sum to u+|S|<u+k , where S is the separator. If just one child is large, its potential alone is at most the parent's. Thus at each depth the sum of the large-node potentials is at most n , while the depth of a large-node branch is at most n . The small leaves contribute at most two children per large node, in addition to a possible small root. Every separator and every small leaf has order at most 2k . Its expected intersection size with W is at most 2kp≤r/1000 . Lemma 7 and a union bound over the decomposition show that, with probability 1-o(1) , all these intersections have fewer than r/100 vertices. If every k -connected leaf had expected fractional chromatic number at most r/4 after restriction to W , the same lemma would give, again with probability 1-o(1) , fractional chromatic number less than 3r/10 in every such leaf. A small leaf has this latter bound as well, since its fractional chromatic number is at most its order. Fix an outcome satisfying all these conclusions. Write F=P[W] . The assumption of the lemma gives f(F)>r/2 , whereas every leaf restriction has fractional chromatic number less than 3r/10 . We compare these bounds by replacing every vertex of F with a clique of the same large order. Ordinary-chromatic connectivity extraction in this larger graph will produce a subgraph of large chromatic number that cannot cross any of the blown-up separators. It must lie in one blown-up leaf, giving the contradiction. For a positive integer m , form F^ (m) by replacing each vertex of F with a clique of order m , and replacing each edge with a complete join between its two replacement cliques. Every color class of F^ (m) projects to a stable set of F and uses at most one vertex of each replacement clique. Dividing the multiplicities of these projected stable sets by m therefore gives a fractional coloring of F . Consequently χ(F^ (m) )≥mf(F)>mr/2. For each leaf restriction, choose a fractional coloring of weight less than 3r/10 . Round its finitely many stable-set weights up to multiples of 1/m . Give a distinct color slot to each unit of weight 1/m . Every original vertex belongs to at least m slots, so its m copies can be assigned distinct slots containing that vertex. A slot is a stable set upstairs: it contains at most one copy of any original vertex, and its original vertices form a stable set. The rounding adds only a bounded number of slots, independent of m for this fixed leaf. There are finitely many leaves, so for all sufficiently large m , every blown-up leaf restriction has a coloring with fewer than 31mr/100 colors. Apply Theorem 2.2 ([Ordinary-chromatic connectivity extraction]) to F^ (m) with the integer parameter k'= mr/50 . For sufficiently large m , exceeds 7k' . We obtain a k' -connected subgraph J with χ(J)≥χ(F^ (m) )-6k' >(19mr)/(50)-6 >(31mr)/(100). Each restricted separator of the decomposition has fewer than r/100 vertices, so its blow-up has fewer than mr/100<k' vertices. Thus J cannot meet both exclusive sides of any such split: deleting its vertices in the separator would disconnect J with fewer than k' deletions. Nor can J be contained in the separator, because its order is greater than k' . Descending the decomposition places J inside a single blown-up leaf restriction, contradicting that leaf's coloring bound. It follows that some k -connected leaf satisfies . This argument also covers the case where P is too small to be k -connected: if all leaves were small, the same contradiction would apply. Finally, the blow-up is only an auxiliary graph for the extraction theorem, which requires no minor exclusion; no bound on its clique-minor number was used.