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

Proof of `The pebble game characterization of Weisfeiler–Leman` (1st 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

We show that kk-WL already distinguishes GG and HH after exactly rr rounds. Otherwise all round-rr color classes have equal sizes, so ∣V(G)∣=∣V(H)∣|V(G)| = |V(H)|, and Duplicator survives rr rounds with the invariant that, for every pebble Spoiler may lift, the remaining placed pebble pairs lie on two kk-tuples with equal round-ss colors (ss the number of remaining rounds). Equality of round-(s+1)(s+1) colors yields a bijection matching the substituted color tuples, which keeps the new state a partial isomorphism (using k≥2k ≥ 2) and, via the invariance of colors under reindexing tuples, re-establishes the invariant.