Proof of `An upper bound on the size of homomorphism witnesses for uncolored graphs`
groundedproofs/Lax119563Proofs/UpperBound/UncoloredWitnessUpperBound.lean · lax-119563
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
Give and the constant color (on vertex sets , ); homomorphism counts from graphs with constant color are the uncolored ones. A graph of treewidth at most with therefore shows, via the homomorphism characterization of -WL, that -WL distinguishes the colored versions. The colored witness size upper bound yields a colored witness of treewidth at most with at most vertices. Every vertex of has color , since otherwise ; so the underlying graph of is the required witness.