While this submission is a draft, it cannot be used by other submissions.

Proof of `The pebble game characterization of Weisfeiler–Leman` (3rd statement)

groundedproofs/Lax119563Proofs/Game/Characterization.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.

Read the Lean proof on GitHub

Description

If the vertex numbers differ Spoiler wins at once. Otherwise Spoiler uses the first kk rounds to place pebbles 0,…,k−10, …, k-1 one by one, always choosing a vertex for which the number of extensions of the placed prefix with a fixed round-rr color differs between GG and HH; this ends in tuples with different round-rr colors. From such tuples Spoiler wins within rr 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 kk pebbles carrying a pair of tuples with different round-(r−1)(r-1) colors.