Proof of `The sparse-house trichotomy`
groundedproofs/Lax57Proofs/SparseHouseTrichotomy.lean · lax-57
What this proof establishes
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
Use the prepared blockade from Claim 7.1.1. A vertex mixed on at least a fraction of the blocks cannot meet a complete pair among them, because anticonnectivity would supply four vertices that, together with it, induce a house. Their union gives the sparser outcome. Otherwise, double-counting mixed incidences finds a block with few mixed outside vertices. The original sparsity bound and the size of the prepared blockade leave a large set anticomplete to that block, giving the peel outcome.
Attribution
Lemma 7.1 of Nguyen, Scott, and Seymour, including the house construction shown in their Figure 2.