AFTD Auto-Formalizing Theoretical Domains

supertoken_graph_bipartite

theoremverifiedformalization

Let G be a finite bipartite simple graph on vertex type V with decidable equality (satisfying G.IsBipartite). Let s ≥ 1 and 1 ≤ k ≤ s * Fintype.card V. Then the supertoken graph supertoken_graph G k s is bipartite (satisfies SimpleGraph.IsBipartite).

Statement

theorem supertoken_graph_bipartite {V : Type*} [DecidableEq V] [Fintype V]
    (G : SimpleGraph V) (hG : G.IsBipartite)
    (s : ℕ) (hs : 1 ≤ s) (k : ℕ) (hk1 : 1 ≤ k) (hk2 : k ≤ s * Fintype.card V) :
    (supertoken_graph G k s).IsBipartite
Formalizes
arXiv:2611.06275 Theorem 2.5 -- On generalized k-token graphs with distinguishable tokens and a maximum capacity of s tokens per vertex
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • supertoken_graphThe supertoken graph F^s_{k x 1}(G) of a simple graph G has as vertices the k-tuples of vertices of G with at most s occurrences of any…
  • OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…

Read back from the Lean

Let $V$ be a finite type with decidable equality, and let $G$ be a bipartite simple graph on $V$. Let $s$ and $k$ be natural numbers such that $1 \le s$, $1 \le k$, and $k \le s \cdot |V|$. Then the supertoken graph of $G$ with parameters $k$ and $s$, supertoken_graph G k s, is bipartite.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To prove that the supertoken graph is bipartite, choose a bipartition (S, T) of the underlying graph G and 2-color configurations according to the parity of the number of tokens placed on S. Since an adjacent configuration differs by moving exactly one token along an edge of G, that token crosses between S and T while all other tokens remain in place. Consequently, the token count on S changes by ±1, flipping the parity and ensuring that every edge connects an even configuration to an odd configuration.

  1. The number of tokens of configuration x in S decomposes into the contribution of coordinate i and the count over all other coordinates.

    The universe of indices is rewritten as the union of {i} and the remaining indices using Finset.insert_erase and Finset.mem_univ. Filtering this set distributes across insertion via Finset.filter_insert. A case split on whether x i ∈ S resolves the cardinality: if true, Finset.card_insert_of_notMem and if_pos show the size increases by 1, with omega simplifying the sum; if false, simp reduces the count to that of the remaining coordinates plus 0.

    lines 7–12

    uses Finset.insert_erase, Finset.mem_univ, Finset.filter_insert, if_pos, Finset.card_insert_of_notMem

      conv_lhs => rw [← Finset.insert_erase (Finset.mem_univ i)]
      rw [Finset.filter_insert]
      by_cases hp : x i ∈ S
      · rw [if_pos hp, Finset.card_insert_of_notMem (by simp), if_pos hp]
        omega
      · simp [hp]
  2. For configurations x and y agreeing on all coordinates except i, the token counts in S on the remaining coordinates are equal.

    Decompose the token counts in S for x and y at coordinate i using supertoken_graph_bipartite_count_split. For any coordinate j distinct from i, the configurations satisfy x j = y j by hypothesis, using Finset.ne_of_mem_erase. Congruence of filtering with Finset.filter_congr then shows that the filtered sub-finsets on indices other than i are identical, so their cardinalities coincide.

    lines 21–28

    uses supertoken_graph_bipartite_count_split, Finset.filter_congr, Finset.ne_of_mem_erase

      have hx := supertoken_graph_bipartite_count_split S x i
      have hy := supertoken_graph_bipartite_count_split S y i
      have hrest : ((Finset.univ.erase i).filter (fun j => y j ∈ S)).card
          = ((Finset.univ.erase i).filter (fun j => x j ∈ S)).card := by
        congr 1
        apply Finset.filter_congr
        intro j hj
        rw [hxy j (Finset.ne_of_mem_erase hj)]
  3. If two configurations differ only at coordinate i and that token crosses the boundary of S, the sum of their token counts in S is odd.

    Substitute the count splittings of x and y and the equality of counts on the remaining indices. The sum becomes the sum of the two indicators at coordinate i plus twice the count on the remaining coordinates. Since the token at i crosses S, one configuration has its token in S and the other does not (analyzed via if_pos and if_neg), so the sum of the indicators is 1. The total sum is therefore 2 * (count on the rest) + 1, which ring arithmetic proves is odd.

    lines 29–34

    uses if_pos, if_neg

      rw [hx, hy, hrest]
      obtain ⟨ha, hb⟩ | ⟨ha, hb⟩ := h
      · rw [if_pos ha, if_neg hb]
        exact ⟨_, by ring⟩
      · rw [if_neg ha, if_pos hb]
        exact ⟨_, by ring⟩
  4. To show the supertoken graph is bipartite, it suffices to show that configurations with an even number of tokens in S and those with an odd number of tokens in S form a valid bipartition.

    Since the base graph G is bipartite, let (S, T) be a bipartition of G. Define a 2-coloring of the configurations by the parity of the number of tokens lying in S. By SimpleGraph.IsBipartiteWith.isBipartite, proving the supertoken graph is bipartite reduces to showing that the even and odd configuration classes are disjoint and that every edge connects an even configuration to an odd configuration.

    lines 41–46

    uses SimpleGraph.IsBipartiteWith.isBipartite

      classical
      obtain ⟨S, T, hST⟩ := hG.exists_isBipartiteWith
      -- Parity colouring: the parity of the number of tokens on the part `S`.
      let cnt : (Fin k → V) → ℕ := fun x => (Finset.univ.filter (fun i => x i ∈ S)).card
      refine SimpleGraph.IsBipartiteWith.isBipartite (s := {x | Even (cnt x.1)})
        (t := {x | Odd (cnt x.1)}) ⟨?_, ?_⟩
  5. The set of even configurations and the set of odd configurations are disjoint.

    Rewriting disjointness via Set.disjoint_left, suppose a configuration had a token count in S that was both even and odd. By Nat.not_even_iff_odd.mpr, an odd natural number is not even, yielding an immediate contradiction.

    lines 47–49

    uses Set.disjoint_left, Nat.not_even_iff_odd.mpr

      · rw [Set.disjoint_left]
        intro x hx hx'
        exact (Nat.not_even_iff_odd.mpr hx') hx
  6. Along any edge of the supertoken graph, the single moved token crosses between S and its complement.

    An edge between configurations x and y corresponds to moving a single token at some coordinate i along an edge of G while leaving all other coordinates unchanged. Because (S, T) is a bipartition of G, the edge has one endpoint in S and the other in T. Since S and T are disjoint (Set.disjoint_right.mp), an endpoint in T cannot be in S. Thus, either x i ∈ S and y i ∉ S (via Or.inl), or x i ∉ S and y i ∈ S (via Or.inr).

    lines 50–56

    uses Or.inl, Or.inr, Set.disjoint_right.mp

      · rintro x y ⟨i, hi, hxy⟩
        -- the unique moved token crosses the bipartition, so it lies in `S` on exactly one side
        have hm := hST.mem_of_adj hi
        have hmem : (x.1 i ∈ S ∧ y.1 i ∉ S) ∨ (x.1 i ∉ S ∧ y.1 i ∈ S) := by
          obtain ⟨h1, h2⟩ | ⟨h1, h2⟩ := hm
          · exact Or.inl ⟨h1, Set.disjoint_right.mp hST.disjoint h2⟩
          · exact Or.inr ⟨Set.disjoint_right.mp hST.disjoint h1, h2⟩
  7. The sum of the token counts in S for adjacent configurations is odd, so one count is odd if and only if the other is even.

    Applying supertoken_graph_bipartite_count_odd to x, y, and the crossing coordinate i shows that the sum of their token counts in S is odd. By Nat.odd_add.mp, the sum of two natural numbers is odd if and only if their parities are opposite.

    lines 57–58

    uses supertoken_graph_bipartite_count_odd, Nat.odd_add.mp

        have hodd := supertoken_graph_bipartite_count_odd x.1 y.1 i hxy hmem
        have hn := Nat.odd_add.mp hodd
  8. Every edge of the supertoken graph connects an even configuration to an odd configuration.

    Split into cases on whether the token count in S for x is even. If it is even, it is not odd (by Nat.not_even_iff_odd.mpr), so the parity equivalence implies the count for y is not even, meaning by Nat.not_even_iff_odd.mp that y is odd. If x is not even, then by Nat.not_even_iff_odd.mp it is odd, and the parity equivalence directly implies that y is even. In either case, the edge connects an even configuration to an odd configuration.

    lines 59–66

    uses Nat.not_even_iff_odd.mpr, Nat.not_even_iff_odd.mp

        by_cases hcx : Even (cnt x.1)
        · left
          refine ⟨hcx, ?_⟩
          have hno : ¬ Odd (cnt x.1) := fun h => (Nat.not_even_iff_odd.mpr h) hcx
          exact Nat.not_even_iff_odd.mp (fun h => hno (hn.mpr h))
        · right
          refine ⟨Nat.not_even_iff_odd.mp hcx, ?_⟩
          exact hn.mp (Nat.not_even_iff_odd.mp hcx)
Finset.insert_erase
Inserting an element a into a finset s with a removed recovers s, provided a ∈ s.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
Finset.filter_insert
Filtering an inserted finset conditionally inserts the element depending on whether it satisfies the predicate.
if_pos
An if-then-else expression evaluates to the then-branch when the condition is true.
Finset.card_insert_of_notMem
Inserting an element not belonging to a finset increases its cardinality by 1.
supertoken_graph_bipartite_count_split
The number of tokens of a configuration lying in S splits into the indicator of whether the i-th coordinate lies in S plus the number of remaining tokens in S.
Finset.filter_congr
Two filtered finsets are equal if their filtering predicates are equivalent on all elements of the finset.
Finset.ne_of_mem_erase
An element belonging to a finset with a removed is not equal to a.
if_neg
An if-then-else expression evaluates to the else-branch when the condition is false.
SimpleGraph.IsBipartiteWith.isBipartite
A graph that admits a bipartition into two subsets is bipartite.
Set.disjoint_left
Two sets are disjoint if and only if no element belongs to both.
Nat.not_even_iff_odd.mpr
If a natural number is odd, then it is not even.
Or.inl
First disjunct injection for a logical disjunction.
Or.inr
Second disjunct injection for a logical disjunction.
Set.disjoint_right.mp
If two sets are disjoint, any element in the second does not belong to the first.
supertoken_graph_bipartite_count_odd
If two configurations differ only at coordinate i and that token crosses the boundary of S, the total number of tokens in S across both configurations is odd.
Nat.odd_add.mp
The sum of two natural numbers is odd if and only if one is odd and the other is even.
Nat.not_even_iff_odd.mp
If a natural number is not even, then it is odd.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Splitting the number of tokens of a configuration lying in `S` off at a single coordinate. -/private lemma supertoken_graph_bipartite_count_split {V : Type*} (S : Set V) [DecidablePred (· ∈ S)]    {k : ℕ} (x : Fin k → V) (i : Fin k) :    (Finset.univ.filter (fun j => x j ∈ S)).card      = (if x i ∈ S then 1 else 0) +        ((Finset.univ.erase i).filter (fun j => x j ∈ S)).card := by  conv_lhs => rw [← Finset.insert_erase (Finset.mem_univ i)]  rw [Finset.filter_insert]  by_cases hp : x i ∈ S  · rw [if_pos hp, Finset.card_insert_of_notMem (by simp), if_pos hp]    omega  · simp [hp]/-- If two configurations differ only at a coordinate `i` whose token crosses `S` in one direction,then the total number of tokens lying in `S` over the two configurations is odd. -/private lemma supertoken_graph_bipartite_count_odd {V : Type*} {k : ℕ} {S : Set V}    [DecidablePred (· ∈ S)] (x y : Fin k → V) (i : Fin k) (hxy : ∀ j, j ≠ i → x j = y j)    (h : (x i ∈ S ∧ y i ∉ S) ∨ (x i ∉ S ∧ y i ∈ S)) :    Odd ((Finset.univ.filter (fun j => x j ∈ S)).card +      (Finset.univ.filter (fun j => y j ∈ S)).card) := by  have hx := supertoken_graph_bipartite_count_split S x i  have hy := supertoken_graph_bipartite_count_split S y i  have hrest : ((Finset.univ.erase i).filter (fun j => y j ∈ S)).card      = ((Finset.univ.erase i).filter (fun j => x j ∈ S)).card := by    congr 1    apply Finset.filter_congr    intro j hj    rw [hxy j (Finset.ne_of_mem_erase hj)]  rw [hx, hy, hrest]  obtain ⟨ha, hb⟩ | ⟨ha, hb⟩ := h  · rw [if_pos ha, if_neg hb]    exact ⟨_, by ring⟩  · rw [if_neg ha, if_pos hb]    exact ⟨_, by ring⟩/-- Theorem 2.5: If G is bipartite, then F^s_{k x 1}(G) is bipartite for every admissible k, s. -/theorem supertoken_graph_bipartite {V : Type*} [DecidableEq V] [Fintype V]    (G : SimpleGraph V) (hG : G.IsBipartite)    (s : ℕ) (hs : 1 ≤ s) (k : ℕ) (hk1 : 1 ≤ k) (hk2 : k ≤ s * Fintype.card V) :    (supertoken_graph G k s).IsBipartite := by  classical  obtain ⟨S, T, hST⟩ := hG.exists_isBipartiteWith  -- Parity colouring: the parity of the number of tokens on the part `S`.  let cnt : (Fin k → V) → ℕ := fun x => (Finset.univ.filter (fun i => x i ∈ S)).card  refine SimpleGraph.IsBipartiteWith.isBipartite (s := {x | Even (cnt x.1)})    (t := {x | Odd (cnt x.1)}) ⟨?_, ?_⟩  · rw [Set.disjoint_left]    intro x hx hx'    exact (Nat.not_even_iff_odd.mpr hx') hx  · rintro x y ⟨i, hi, hxy⟩    -- the unique moved token crosses the bipartition, so it lies in `S` on exactly one side    have hm := hST.mem_of_adj hi    have hmem : (x.1 i ∈ S ∧ y.1 i ∉ S) ∨ (x.1 i ∉ S ∧ y.1 i ∈ S) := by      obtain ⟨h1, h2⟩ | ⟨h1, h2⟩ := hm      · exact Or.inl ⟨h1, Set.disjoint_right.mp hST.disjoint h2⟩      · exact Or.inr ⟨Set.disjoint_right.mp hST.disjoint h1, h2⟩    have hodd := supertoken_graph_bipartite_count_odd x.1 y.1 i hxy hmem    have hn := Nat.odd_add.mp hodd    by_cases hcx : Even (cnt x.1)    · left      refine ⟨hcx, ?_⟩      have hno : ¬ Odd (cnt x.1) := fun h => (Nat.not_even_iff_odd.mpr h) hcx      exact Nat.not_even_iff_odd.mp (fun h => hno (hn.mpr h))    · right      refine ⟨Nat.not_even_iff_odd.mp hcx, ?_⟩      exact hn.mp (Nat.not_even_iff_odd.mp hcx)
See it in the graphDiscuss this resultChallenge it