Proof of `The pebble game characterization of Weisfeiler–Leman` (1st statement)
groundedproofs/Lax119563Proofs/Game/Characterization.lean · lax-119563
What this proof establishes
no assumptions
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
We show that -WL already distinguishes and after exactly rounds. Otherwise all round- color classes have equal sizes, so , and Duplicator survives rounds with the invariant that, for every pebble Spoiler may lift, the remaining placed pebble pairs lie on two -tuples with equal round- colors ( the number of remaining rounds). Equality of round- colors yields a bijection matching the substituted color tuples, which keeps the new state a partial isomorphism (using ) and, via the invariance of colors under reindexing tuples, re-establishes the invariant.