simple_graph_leap_group_bipartite_ne_top
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.
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.
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
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.
uses
simple_graph_leap_group_bipartite_ne_top_fin2_eqdef 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)
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.
uses
Ne.symminv_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
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.
uses
Subgroup.closure_lelemma 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
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.
uses
Equiv.swap_apply_left,Equiv.swap_apply_of_ne_of_nelemma 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
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.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.card_le_card,Finset.card_le_two,Finset.card_univlemma 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
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.
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_toptheorem 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)
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.
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.
- In Step 1, the equivalence for Fin 2 is verified by exhaustive case evaluation using fin_cases and decide.
- In Step 6 and Step 7, Presburger arithmetic goals (such as deriving |V| ≥ 3 and |V| > 0 from |V| ≥ 4) are closed automatically by omega.
- The split into cases where a hop exists versus where no hops exist is a formal necessity in Lean: when the set of hops is empty, its subgroup closure is the bottom subgroup ⊥ by definition.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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