Proof of `The pebble game characterization of Weisfeiler–Leman` (3rd 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
If the vertex numbers differ Spoiler wins at once. Otherwise Spoiler uses the first rounds to place pebbles one by one, always choosing a vertex for which the number of extensions of the placed prefix with a fixed round- color differs between and ; this ends in tuples with different round- colors. From such tuples Spoiler wins within more rounds by induction: he places the free pebble on a vertex where the substituted color tuples differ under Duplicator's bijection and continues with the pebbles carrying a pair of tuples with different round- colors.