Proof of `Independent-set encodings satisfy the relaxation` (1st statement)
groundedproofs/Lax263307Proofs/RelaxationFeasibility.lean · lax-263307
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
The exact independent-set hull satisfies all relaxation constraints.
Proof strategy
The feasible set is convex because all five constraint families are linear. It contains every independent-set indicator, hence their convex hull.
Attribution
Bonnet–Chang, Section 5.1, equation (20).