AFTD Auto-Formalizing Theoretical Domains

simple_graph_leap_group_bipartite_ne_top

theoremverifiedformalization

Let G be a bipartite simple graph on a finite vertex set with at least 4 vertices. Then its leap group Λ₁(G) is not the full symmetric group on its vertices.

Statement

theorem simple_graph_leap_group_bipartite_ne_top
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    (h_card : 4 ≤ Fintype.card V)
    (h_bip : G.IsBipartite) :
    simple_graph_leap_group G ≠ ⊤
Formalizes
scout/2610-18463-the-group-generated-by-a-graph-s-derangements.md:259
Verified
15 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • simple_graph_leap_groupThe leap group Λ₁(G) of a graph G: the subgroup of the symmetric group on the vertices generated by the hops of G.
  • simple_graph_is_hopA hop (graph derangement) of a graph G is a permutation h of the vertices that sends every vertex v to a neighbour h(v) of v.

Read back from the Lean

For any finite type $V$ with decidable equality such that the cardinality of $V$ is at least 4, and for any simple graph $G$ on $V$, if $G$ is bipartite, then the leap group of $G$ is not the top subgroup of the symmetric group on $V$ (i.e., simple_graph_leap_group G ≠ ⊤ in Subgroup (Equiv.Perm V)).

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

The leap group Λ₁(G) is generated by hops, which are permutations mapping every vertex to an adjacent one. In a bipartite graph with 2-coloring c, every hop must swap the two color classes, so Λ₁(G) is contained in the subgroup of permutations that either preserve or swap both colors everywhere. When hops exist, choosing an adjacent pair u, v and a third vertex w (which exists since |V| ≥ 4) yields a transposition (u v) that neither preserves nor swaps colors everywhere, placing it outside the leap group and showing Λ₁(G) ≠ ⊤. When no hops exist, Λ₁(G) is the trivial subgroup ⊥, which cannot be the full symmetric group since |V| ≥ 4 ≥ 2.

  1. In Fin 2, any two elements distinct from a middle element are equal. automation

    Since Fin 2 contains only two elements, if x ≠ y and y ≠ z, then x must equal z. The proof verifies this by exhausting all 2³ = 8 possible valuations of x, y, z with fin_cases and decide.

    lines 1–3

    lemma simple_graph_leap_group_bipartite_ne_top_fin2_eq {x y z : Fin 2} (h1 : x ≠ y) (h2 : y ≠ z) : x = z := by
      revert h1 h2
      fin_cases x <;> fin_cases y <;> fin_cases z <;> decide
  2. The identity preserves colors, and permutations that preserve or swap colors everywhere are closed under composition.

    The identity permutation preserves colors trivially. For composition, given permutations a and b that each either preserve colors everywhere or swap colors everywhere, we case-split on the four possibilities. If both preserve, their composition preserves. If one preserves and one swaps, their composition swaps. If both swap, then composing two color swaps returns each vertex to its original color by simple_graph_leap_group_bipartite_ne_top_fin2_eq, so their composition preserves.

    lines 8–18

    uses simple_graph_leap_group_bipartite_ne_top_fin2_eq

    def simple_graph_leap_group_bipartite_ne_top_subgroup {V : Type*} (c : V → Fin 2) : Subgroup (Equiv.Perm V) where
      carrier := {g | simple_graph_leap_group_bipartite_ne_top_preserves_or_swaps c g}
      one_mem' := Or.inl fun _ => rfl
      mul_mem' := by
        intro a b ha hb
        dsimp [simple_graph_leap_group_bipartite_ne_top_preserves_or_swaps] at ha hb ⊢
        rcases ha with ha | ha <;> rcases hb with hb | hb
        · left; intro v; rw [ha, hb]
        · right; intro v; rw [ha]; exact hb v
        · right; intro v; rw [← hb v]; exact ha (b v)
        · left; intro v; exact simple_graph_leap_group_bipartite_ne_top_fin2_eq (ha (b v)) (hb v)
  3. Permutations that preserve or swap colors everywhere are closed under inversion, forming a subgroup of Perm V.

    Given a permutation a in the carrier, evaluating its color action at a⁻¹(v) and simplifying a(a⁻¹(v)) = v shows that if a preserves colors, a⁻¹ preserves colors, and if a swaps colors, a⁻¹ swaps colors (by Ne.symm). Thus the set forms a subgroup of Equiv.Perm V.

    lines 19–24

    uses Ne.symm

      inv_mem' := by
        intro a ha
        dsimp [simple_graph_leap_group_bipartite_ne_top_preserves_or_swaps] at ha ⊢
        rcases ha with ha | ha
        · left; intro v; have := ha (a.symm v); rw [a.apply_symm_apply] at this; exact this.symm
        · right; intro v; have := ha (a.symm v); rw [a.apply_symm_apply] at this; exact Ne.symm this
  4. The leap group Λ₁(G) is contained in the subgroup of color-preserving or color-swapping permutations.

    By Subgroup.closure_le, it suffices to show that every hop h belongs to the subgroup. A hop satisfies G.Adj v (h v) for all v. In a valid bipartite 2-coloring c, adjacent vertices have distinct colors, so c (h v) ≠ c v for all v. Thus every hop swaps colors everywhere, which places every hop in the subgroup.

    lines 26–33

    uses Subgroup.closure_le

    lemma simple_graph_leap_group_bipartite_ne_top_leap_group_le {V : Type*} (G : SimpleGraph V) (c : G.Coloring (Fin 2)) :
        simple_graph_leap_group G ≤ simple_graph_leap_group_bipartite_ne_top_subgroup c := by
      rw [simple_graph_leap_group, Subgroup.closure_le]
      rintro h (hh : simple_graph_is_hop G h)
      dsimp [simple_graph_leap_group_bipartite_ne_top_subgroup, simple_graph_leap_group_bipartite_ne_top_preserves_or_swaps]
      right
      intro v
      exact (c.valid (hh v)).symm
  5. A transposition swapping two vertices of different colors while fixing a third vertex does not belong to the subgroup.

    Suppose Equiv.swap u v belongs to the subgroup, with c u ≠ c v and a third vertex w distinct from u and v. If the swap preserves colors everywhere, evaluating at u yields c v = c u by Equiv.swap_apply_left, contradicting c u ≠ c v. If the swap swaps colors everywhere, evaluating at w yields c w ≠ c w by Equiv.swap_apply_of_ne_of_ne, a contradiction.

    lines 35–47

    uses Equiv.swap_apply_left, Equiv.swap_apply_of_ne_of_ne

    lemma simple_graph_leap_group_bipartite_ne_top_swap_not_mem {V : Type*} [DecidableEq V]
        (c : V → Fin 2) {u v w : V}
        (huv : c u ≠ c v) (hwu : w ≠ u) (hwv : w ≠ v) :
        Equiv.swap u v ∉ simple_graph_leap_group_bipartite_ne_top_subgroup c := by
      intro h
      dsimp [simple_graph_leap_group_bipartite_ne_top_subgroup, simple_graph_leap_group_bipartite_ne_top_preserves_or_swaps] at h
      rcases h with h_pres | h_swap
      · have h1 := h_pres u
        rw [Equiv.swap_apply_left] at h1
        exact huv h1.symm
      · have h2 := h_swap w
        rw [Equiv.swap_apply_of_ne_of_ne hwu hwv] at h2
        exact h2 rfl
  6. In any finite set with at least 3 elements, any two elements admit a third distinct element. automation

    Suppose for contradiction that no such third element exists: then every element in the universe is equal to u or v (using Finset.mem_insert and Finset.mem_singleton), so Finset.univ ⊆ {u, v}. By Finset.card_le_card, Finset.card_univ, and Finset.card_le_two, the cardinality of V is at most 2, contradicting 3 ≤ |V|. Linear arithmetic (omega) finishes the contradiction.

    lines 49–62

    uses Finset.mem_insert, Finset.mem_singleton, Finset.card_le_card, Finset.card_le_two, Finset.card_univ

    lemma simple_graph_leap_group_bipartite_ne_top_exists_ne_pair {V : Type*} [Fintype V] [DecidableEq V]
        (h_card : 3 ≤ Fintype.card V) (u v : V) :
        ∃ w : V, w ≠ u ∧ w ≠ v := by
      by_contra! h
      have h_univ : (Finset.univ : Finset V) ⊆ {u, v} := by
        intro x _
        simp only [Finset.mem_insert, Finset.mem_singleton]
        by_cases hx : x = u
        · left; exact hx
        · right; exact h x hx
      have h_le := Finset.card_le_card h_univ
      have h_two : ({u, v} : Finset V).card ≤ 2 := Finset.card_le_two
      rw [Finset.card_univ] at h_le
      omega
  7. If G admits a hop, its leap group is not the full symmetric group.

    Assume there is a hop h₀. Since |V| ≥ 4 > 0, V is non-empty by Fintype.card_pos_iff.1. Choose an arbitrary vertex u and let v = h₀ u. Because h₀ is a hop, u is adjacent to v, so c u ≠ c v. Since |V| ≥ 4 ≥ 3, simple_graph_leap_group_bipartite_ne_top_exists_ne_pair yields a vertex w distinct from u and v. By simple_graph_leap_group_bipartite_ne_top_swap_not_mem, Equiv.swap u v does not belong to the subgroup of color-preserving or color-swapping permutations, and therefore by simple_graph_leap_group_bipartite_ne_top_leap_group_le it does not belong to Λ₁(G). But if Λ₁(G) = ⊤, the transposition would belong to Λ₁(G) by Subgroup.mem_top, a contradiction.

    lines 65–85

    uses Fintype.card_pos_iff.1, simple_graph_leap_group_bipartite_ne_top_exists_ne_pair, simple_graph_leap_group_bipartite_ne_top_swap_not_mem, simple_graph_leap_group_bipartite_ne_top_leap_group_le, Subgroup.mem_top

    theorem simple_graph_leap_group_bipartite_ne_top
        {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
        (h_card : 4 ≤ Fintype.card V)
        (h_bip : G.IsBipartite) :
        simple_graph_leap_group G ≠ ⊤ := by
      by_cases h_hop : ∃ h, simple_graph_is_hop G h
      · obtain ⟨h0, hh0⟩ := h_hop
        obtain ⟨c⟩ := h_bip
        have : Nonempty V := Fintype.card_pos_iff.1 (by omega)
        inhabit V
        let u : V := default
        let v : V := h0 u
        have huv : c u ≠ c v := c.valid (hh0 u)
        obtain ⟨w, hwu, hwv⟩ := simple_graph_leap_group_bipartite_ne_top_exists_ne_pair (by omega) u v
        have h_not_mem := simple_graph_leap_group_bipartite_ne_top_swap_not_mem c huv hwu hwv
        have h_le := simple_graph_leap_group_bipartite_ne_top_leap_group_le G c
        intro h_top
        have : Equiv.swap u v ∈ simple_graph_leap_group G := by
          rw [h_top]
          exact Subgroup.mem_top _
        exact h_not_mem (h_le this)
  8. If G admits no hops, its leap group is trivial, which cannot be the full symmetric group.

    If no hops exist, the set of hops is empty by Set.eq_empty_iff_forall_notMem, so Λ₁(G) = Subgroup.closure ∅ = ⊥ by Subgroup.closure_empty. If Λ₁(G) = ⊤, then ⊥ = ⊤. Since |V| ≥ 4 > 1, V is nontrivial by Fintype.one_lt_card_iff_nontrivial.1, so there exist two distinct vertices x ≠ y by exists_pair_ne. Then Equiv.swap x y ∈ ⊤ = ⊥ by Subgroup.mem_top, which means Equiv.swap x y = 1 by Subgroup.mem_bot. Applying this permutation to x yields y = x by Equiv.ext_iff.1 and Equiv.swap_apply_left, contradicting x ≠ y.

    lines 86–104

    uses Set.eq_empty_iff_forall_notMem, Subgroup.closure_empty, Fintype.one_lt_card_iff_nontrivial.1, exists_pair_ne, Subgroup.mem_top, Subgroup.mem_bot, Equiv.ext_iff.1, Equiv.swap_apply_left

      · intro h_top
        have h_set : {h : Equiv.Perm V | simple_graph_is_hop G h} = ∅ := by
          rw [Set.eq_empty_iff_forall_notMem]
          intro h hh
          exact h_hop ⟨h, hh⟩
        have h_bot : simple_graph_leap_group G = ⊥ := by
          dsimp [simple_graph_leap_group]
          rw [h_set, Subgroup.closure_empty]
        rw [h_bot] at h_top
        have : Nontrivial V := Fintype.one_lt_card_iff_nontrivial.1 (by omega)
        obtain ⟨x, y, hxy⟩ := exists_pair_ne V
        have h_mem : Equiv.swap x y ∈ (⊥ : Subgroup (Equiv.Perm V)) := by
          rw [h_top]
          exact Subgroup.mem_top _
        rw [Subgroup.mem_bot] at h_mem
        have h_app := Equiv.ext_iff.1 h_mem x
        rw [Equiv.swap_apply_left] at h_app
        change y = x at h_app
        exact hxy h_app.symm
simple_graph_leap_group_bipartite_ne_top_fin2_eq
In a two-element set, if x ≠ y and y ≠ z, then x = z.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Subgroup.closure_le
The subgroup generated by a set k is contained in a subgroup K if and only if k ⊆ K.
Equiv.swap_apply_left
A transposition of a and b maps a to b.
Equiv.swap_apply_of_ne_of_ne
A transposition of a and b fixes any element distinct from both a and b.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
Finset.card_le_card
If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.card_le_two
A pair {a, b} has cardinality at most 2.
Finset.card_univ
The cardinality of the universal finset on a finite type equals the cardinality of the type.
Fintype.card_pos_iff.1
A finite type with strictly positive cardinality is non-empty.
simple_graph_leap_group_bipartite_ne_top_exists_ne_pair
In any finite set with at least 3 elements, for any two elements u and v, there exists a third element distinct from both.
simple_graph_leap_group_bipartite_ne_top_swap_not_mem
If u and v have different colors and w is distinct from both, the transposition (u v) does not belong to the subgroup of color-preserving or color-swapping permutations.
simple_graph_leap_group_bipartite_ne_top_leap_group_le
The leap group of a graph is contained in the subgroup of permutations that preserve or swap the colors of a 2-coloring.
Subgroup.mem_top
Every element belongs to the top (full) subgroup.
Set.eq_empty_iff_forall_notMem
A set is empty if and only if no element belongs to it.
Subgroup.closure_empty
The subgroup generated by the empty set is the trivial subgroup ⊥.
Fintype.one_lt_card_iff_nontrivial.1
A finite type with cardinality strictly greater than 1 is nontrivial.
exists_pair_ne
Every nontrivial type contains two distinct elements.
Subgroup.mem_bot
An element belongs to the trivial subgroup ⊥ if and only if it is the identity 1.
Equiv.ext_iff.1
Two permutations are equal if and only if they agree on all inputs.

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

lemma simple_graph_leap_group_bipartite_ne_top_fin2_eq {x y z : Fin 2} (h1 : x ≠ y) (h2 : y ≠ z) : x = z := by  revert h1 h2  fin_cases x <;> fin_cases y <;> fin_cases z <;> decidedef simple_graph_leap_group_bipartite_ne_top_preserves_or_swaps {V : Type*} (c : V → Fin 2) (g : Equiv.Perm V) : Prop :=  (∀ v, c (g v) = c v) ∨ (∀ v, c (g v) ≠ c v)def simple_graph_leap_group_bipartite_ne_top_subgroup {V : Type*} (c : V → Fin 2) : Subgroup (Equiv.Perm V) where  carrier := {g | simple_graph_leap_group_bipartite_ne_top_preserves_or_swaps c g}  one_mem' := Or.inl fun _ => rfl  mul_mem' := by    intro a b ha hb    dsimp [simple_graph_leap_group_bipartite_ne_top_preserves_or_swaps] at ha hb ⊢    rcases ha with ha | ha <;> rcases hb with hb | hb    · left; intro v; rw [ha, hb]    · right; intro v; rw [ha]; exact hb v    · right; intro v; rw [← hb v]; exact ha (b v)    · left; intro v; exact simple_graph_leap_group_bipartite_ne_top_fin2_eq (ha (b v)) (hb v)  inv_mem' := by    intro a ha    dsimp [simple_graph_leap_group_bipartite_ne_top_preserves_or_swaps] at ha ⊢    rcases ha with ha | ha    · left; intro v; have := ha (a.symm v); rw [a.apply_symm_apply] at this; exact this.symm    · right; intro v; have := ha (a.symm v); rw [a.apply_symm_apply] at this; exact Ne.symm thislemma simple_graph_leap_group_bipartite_ne_top_leap_group_le {V : Type*} (G : SimpleGraph V) (c : G.Coloring (Fin 2)) :    simple_graph_leap_group G ≤ simple_graph_leap_group_bipartite_ne_top_subgroup c := by  rw [simple_graph_leap_group, Subgroup.closure_le]  rintro h (hh : simple_graph_is_hop G h)  dsimp [simple_graph_leap_group_bipartite_ne_top_subgroup, simple_graph_leap_group_bipartite_ne_top_preserves_or_swaps]  right  intro v  exact (c.valid (hh v)).symmlemma simple_graph_leap_group_bipartite_ne_top_swap_not_mem {V : Type*} [DecidableEq V]    (c : V → Fin 2) {u v w : V}    (huv : c u ≠ c v) (hwu : w ≠ u) (hwv : w ≠ v) :    Equiv.swap u v ∉ simple_graph_leap_group_bipartite_ne_top_subgroup c := by  intro h  dsimp [simple_graph_leap_group_bipartite_ne_top_subgroup, simple_graph_leap_group_bipartite_ne_top_preserves_or_swaps] at h  rcases h with h_pres | h_swap  · have h1 := h_pres u    rw [Equiv.swap_apply_left] at h1    exact huv h1.symm  · have h2 := h_swap w    rw [Equiv.swap_apply_of_ne_of_ne hwu hwv] at h2    exact h2 rfllemma simple_graph_leap_group_bipartite_ne_top_exists_ne_pair {V : Type*} [Fintype V] [DecidableEq V]    (h_card : 3 ≤ Fintype.card V) (u v : V) :    ∃ w : V, w ≠ u ∧ w ≠ v := by  by_contra! h  have h_univ : (Finset.univ : Finset V) ⊆ {u, v} := by    intro x _    simp only [Finset.mem_insert, Finset.mem_singleton]    by_cases hx : x = u    · left; exact hx    · right; exact h x hx  have h_le := Finset.card_le_card h_univ  have h_two : ({u, v} : Finset V).card ≤ 2 := Finset.card_le_two  rw [Finset.card_univ] at h_le  omega/-- A bipartite graph on at least 4 vertices cannot have full leap group. -/theorem simple_graph_leap_group_bipartite_ne_top    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    (h_card : 4 ≤ Fintype.card V)    (h_bip : G.IsBipartite) :    simple_graph_leap_group G ≠ ⊤ := by  by_cases h_hop : ∃ h, simple_graph_is_hop G h  · obtain ⟨h0, hh0⟩ := h_hop    obtain ⟨c⟩ := h_bip    have : Nonempty V := Fintype.card_pos_iff.1 (by omega)    inhabit V    let u : V := default    let v : V := h0 u    have huv : c u ≠ c v := c.valid (hh0 u)    obtain ⟨w, hwu, hwv⟩ := simple_graph_leap_group_bipartite_ne_top_exists_ne_pair (by omega) u v    have h_not_mem := simple_graph_leap_group_bipartite_ne_top_swap_not_mem c huv hwu hwv    have h_le := simple_graph_leap_group_bipartite_ne_top_leap_group_le G c    intro h_top    have : Equiv.swap u v ∈ simple_graph_leap_group G := by      rw [h_top]      exact Subgroup.mem_top _    exact h_not_mem (h_le this)  · intro h_top    have h_set : {h : Equiv.Perm V | simple_graph_is_hop G h} = ∅ := by      rw [Set.eq_empty_iff_forall_notMem]      intro h hh      exact h_hop ⟨h, hh⟩    have h_bot : simple_graph_leap_group G = ⊥ := by      dsimp [simple_graph_leap_group]      rw [h_set, Subgroup.closure_empty]    rw [h_bot] at h_top    have : Nontrivial V := Fintype.one_lt_card_iff_nontrivial.1 (by omega)    obtain ⟨x, y, hxy⟩ := exists_pair_ne V    have h_mem : Equiv.swap x y ∈ (⊥ : Subgroup (Equiv.Perm V)) := by      rw [h_top]      exact Subgroup.mem_top _    rw [Subgroup.mem_bot] at h_mem    have h_app := Equiv.ext_iff.1 h_mem x    rw [Equiv.swap_apply_left] at h_app    change y = x at h_app    exact hxy h_app.symm
See it in the graphDiscuss this resultChallenge it