AFTD Auto-Formalizing Theoretical Domains

admissibility_lemma_edge_partition

theoremverified

Let s ≥ 3 and let φ : V → ℕ be a vertex labeling of a finite simple graph G such that every vertex receives label 1 or s. Then the edge set of G is partitioned into the classes of edges with endpoint label sums 2, s + 1, and 2s, so that |E_2| + |E_{s+1}| + |E_{2s}| = |E(G)|.

Statement

open scoped Classical in
theorem admissibility_lemma_edge_partition {V : Type*} [Fintype V]
    (G : SimpleGraph V) (s : ℕ) (hs : 3 ≤ s) (φ : V → ℕ)
    (hφ : ∀ v : V, φ v = 1 ∨ φ v = s) :
    let a := (simple_graph_endpoint_sum_edges G φ 2).card
    let b := (simple_graph_endpoint_sum_edges G φ (s + 1)).card
    let c := (simple_graph_endpoint_sum_edges G φ (2 * s)).card
    a + b + c = G.edgeFinset.card
Source
arXiv:2611.16338, Lemma 2.1
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • simple_graph_endpoint_sum_edgesGiven a finite simple graph G and a vertex labeling φ : V → ℕ, the finset simple_graph_endpoint_sum_edges G φ r consists of all edges uv…

Read back from the Lean

For any finite type $V$, any simple graph $G$ on $V$, any natural number $s$ satisfying $3 \le s$, and any function $\varphi : V \to \mathbb{N}$ such that every vertex $v \in V$ satisfies $\varphi(v) = 1$ or $\varphi(v) = s$: the sum of the cardinalities of: 1. the set of edges of $G$ whose endpoints' labels under $\varphi$ sum to $2$, 2. the set of edges of $G$ whose endpoints' labels under $\varphi$ sum to $s + 1$, and 3. the set of edges of $G$ whose endpoints' labels under $\varphi$ sum to $2s$, is equal to the total number of edges of $G$ (the cardinality of G.edgeFinset).

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 proof first establishes a general partition lemma for finite sets: if a function on a finite set takes only three distinct values, the set partitions into three disjoint fibers whose cardinalities sum to the total cardinality. For the main theorem, since every vertex is labeled 1 or s and s ≥ 3, the three target sums 2, s + 1, and 2s are strictly distinct. Evaluating the endpoint label sum on each of the four possible label pairs of an edge shows that every edge has endpoint sum in {2, s + 1, 2s}, so applying the three-fiber lemma immediately gives |E₂| + |E_{s+1}| + |E_{2s}| = |E(G)|.

  1. Define A, B, and C as the fibers of s on which f equals r₁, r₂, and r₃ respectively.

    We define A, B, and C as the sub-finsets of s where f takes values r₁, r₂, and r₃ respectively.

    lines 8–10

      set A := s.filter (fun x => f x = r1)
      set B := s.filter (fun x => f x = r2)
      set C := s.filter (fun x => f x = r3)
  2. The sets A, B, and C are pairwise disjoint.

    By Finset.disjoint_filter, two filtered sub-finsets are disjoint if no element satisfies both conditions. If an element x ∈ s were in both A and B, we would have f x = r₁ and f x = r₂, implying r₁ = r₂, which contradicts r₁ ≠ r₂. Disjointness of (A, C) and (B, C) follows identically using r₁ ≠ r₃ and r₂ ≠ r₃.

    lines 11–25

    uses Finset.disjoint_filter

      have dAB : Disjoint A B := by
        rw [Finset.disjoint_filter]
        intro x _ hx1 hx2
        subst hx1 hx2
        exact h12 rfl
      have dAC : Disjoint A C := by
        rw [Finset.disjoint_filter]
        intro x _ hx1 hx3
        subst hx1 hx3
        exact h13 rfl
      have dBC : Disjoint B C := by
        rw [Finset.disjoint_filter]
        intro x _ hx2 hx3
        subst hx2 hx3
        exact h23 rfl
  3. The union A ∪ B is disjoint from C, and |(A ∪ B) ∪ C| = |A| + |B| + |C|.

    Since A and B are both disjoint from C, their union A ∪ B is disjoint from C by Finset.disjoint_union_left. Since A and B are disjoint, |A ∪ B| = |A| + |B| by Finset.card_union_of_disjoint; applying the same lemma to (A ∪ B) and C yields |(A ∪ B) ∪ C| = |A| + |B| + |C|.

    lines 26–31

    uses Finset.disjoint_union_left, Finset.card_union_of_disjoint

      have d_union : Disjoint (A ∪ B) C := by
        rw [Finset.disjoint_union_left]
        exact ⟨dAC, dBC⟩
      have h_card_AB : (A ∪ B).card = A.card + B.card := Finset.card_union_of_disjoint dAB
      have h_card_all : ((A ∪ B) ∪ C).card = (A ∪ B).card + C.card := Finset.card_union_of_disjoint d_union
      rw [h_card_AB] at h_card_all
  4. The union (A ∪ B) ∪ C equals s, and therefore |A| + |B| + |C| = |s|.

    By Finset.filter_or, (A ∪ B) ∪ C is the sub-finset of elements x ∈ s satisfying f x = r₁ ∨ f x = r₂ ∨ f x = r₃. By assumption, every element of s satisfies this disjunction, so Finset.filter_true_of_mem shows that this union equals s. Substituting this into the cardinality formula from the previous step yields |A| + |B| + |C| = |s|.

    lines 32–44

    uses Finset.filter_or, Finset.filter_true_of_mem

      have h_union : (A ∪ B) ∪ C = s := by
        have h_or : (A ∪ B) ∪ C = s.filter (fun x => (f x = r1 ∨ f x = r2) ∨ f x = r3) := by
          simp only [A, B, C, Finset.filter_or]
        rw [h_or]
        apply Finset.filter_true_of_mem
        intro x hx
        rcases hall x hx with h1 | h2 | h3
        · left; left; exact h1
        · left; right; exact h2
        · right; exact h3
      rw [h_union] at h_card_all
      change A.card + B.card + C.card = s.card
      linarith
  5. The goal reduces to showing that the edge fibers for endpoint sums 2, s + 1, and 2s partition E(G).

    We introduce names for the cardinalities of the edge subsets with endpoint sums 2, s + 1, and 2s, and unfold the definition of simple_graph_endpoint_sum_edges to express each class as a fiber of the endpoint sum function on the edge set of G.

    lines 55–59

    uses simple_graph_endpoint_sum_edges

      intro a b c
      change (simple_graph_endpoint_sum_edges G φ 2).card +
        (simple_graph_endpoint_sum_edges G φ (s + 1)).card +
        (simple_graph_endpoint_sum_edges G φ (2 * s)).card = G.edgeFinset.card
      simp only [simple_graph_endpoint_sum_edges]
  6. By the three-fiber partition lemma, it suffices to show that every edge has endpoint label sum in {2, s + 1, 2s}.

    We apply admissibility_lemma_edge_partition_three_fibers to the edge set E(G) and the endpoint sum function with targets 2, s + 1, and 2s. The requirement that these three targets are pairwise distinct (2 ≠ s + 1, 2 ≠ 2s, and s + 1 ≠ 2s) is verified by linear integer arithmetic using the hypothesis s ≥ 3.

    lines 60–65

    uses admissibility_lemma_edge_partition_three_fibers

      apply admissibility_lemma_edge_partition_three_fibers G.edgeFinset
        (fun e => Sym2.lift ⟨fun u v => φ u + φ v, fun _ _ => add_comm _ _⟩ e)
        2 (s + 1) (2 * s)
      · omega
      · omega
      · omega
  7. Every edge of G has endpoint label sum 2, s + 1, or 2s.

    We represent an arbitrary edge e ∈ E(G) as an unordered pair {u, v} via Sym2.inductionOn. Since each vertex label φ u and φ v is either 1 or s, there are four cases: if both are 1, the sum is 2; if one is 1 and the other is s, the sum is s + 1 (using add_comm); and if both are s, the sum is s + s = 2s by two_mul. In every case the sum is in {2, s + 1, 2s}.

    lines 66–73

    uses Sym2.inductionOn, add_comm, two_mul

      · intro e he
        refine Sym2.inductionOn e fun u v => ?_
        dsimp
        rcases hφ u with hu | hu <;> rcases hφ v with hv | hv
        · left; rw [hu, hv]
        · right; left; rw [hu, hv, add_comm]
        · right; left; rw [hu, hv]
        · right; right; rw [hu, hv, two_mul]
Finset.disjoint_filter
Two filtered sub-finsets {x ∈ s | p x} and {x ∈ s | q x} are disjoint if and only if no element of s satisfies both predicates p and q.
Finset.disjoint_union_left
A union s ∪ t is disjoint from u if and only if both s and t are disjoint from u.
Finset.card_union_of_disjoint
If two finite sets are disjoint, the cardinality of their union is the sum of their cardinalities.
Finset.filter_or
Filtering a finite set by a disjunction p ∨ q produces the union of the set filtered by p and the set filtered by q.
Finset.filter_true_of_mem
If every element of a finite set s satisfies property p, then filtering s by p yields s itself.
simple_graph_endpoint_sum_edges
The finite set of edges of a graph whose endpoints have label sum r under a given vertex labeling.
admissibility_lemma_edge_partition_three_fibers
If a function on a finite set takes values only among three pairwise distinct values, the cardinalities of the three corresponding fibers sum to the cardinality of the whole set.
Sym2.inductionOn
To prove a proposition for an unordered pair in Sym2 α, it suffices to prove it for pairs of the form s(x, y).
add_comm
Addition is commutative: a + b = b + a.
two_mul
Multiplication by 2 satisfies 2 * n = n + n.

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

private lemma admissibility_lemma_edge_partition_three_fibers    {α : Type*} [DecidableEq α] (s : Finset α) (f : α → ℕ) (r1 r2 r3 : ℕ)    (h12 : r1 ≠ r2) (h13 : r1 ≠ r3) (h23 : r2 ≠ r3)    (hall : ∀ x ∈ s, f x = r1 ∨ f x = r2 ∨ f x = r3) :    (s.filter (fun x => f x = r1)).card +    (s.filter (fun x => f x = r2)).card +    (s.filter (fun x => f x = r3)).card = s.card := by  set A := s.filter (fun x => f x = r1)  set B := s.filter (fun x => f x = r2)  set C := s.filter (fun x => f x = r3)  have dAB : Disjoint A B := by    rw [Finset.disjoint_filter]    intro x _ hx1 hx2    subst hx1 hx2    exact h12 rfl  have dAC : Disjoint A C := by    rw [Finset.disjoint_filter]    intro x _ hx1 hx3    subst hx1 hx3    exact h13 rfl  have dBC : Disjoint B C := by    rw [Finset.disjoint_filter]    intro x _ hx2 hx3    subst hx2 hx3    exact h23 rfl  have d_union : Disjoint (A ∪ B) C := by    rw [Finset.disjoint_union_left]    exact ⟨dAC, dBC⟩  have h_card_AB : (A ∪ B).card = A.card + B.card := Finset.card_union_of_disjoint dAB  have h_card_all : ((A ∪ B) ∪ C).card = (A ∪ B).card + C.card := Finset.card_union_of_disjoint d_union  rw [h_card_AB] at h_card_all  have h_union : (A ∪ B) ∪ C = s := by    have h_or : (A ∪ B) ∪ C = s.filter (fun x => (f x = r1 ∨ f x = r2) ∨ f x = r3) := by      simp only [A, B, C, Finset.filter_or]    rw [h_or]    apply Finset.filter_true_of_mem    intro x hx    rcases hall x hx with h1 | h2 | h3    · left; left; exact h1    · left; right; exact h2    · right; exact h3  rw [h_union] at h_card_all  change A.card + B.card + C.card = s.card  linarithopen scoped Classical in/-- A binary {1, s}-labeling partitions E(G) into classes E_2, E_{s+1}, E_{2s}. -/theorem admissibility_lemma_edge_partition {V : Type*} [Fintype V]    (G : SimpleGraph V) (s : ℕ) (hs : 3 ≤ s) (φ : V → ℕ)    (hφ : ∀ v : V, φ v = 1 ∨ φ v = s) :    let a := (simple_graph_endpoint_sum_edges G φ 2).card    let b := (simple_graph_endpoint_sum_edges G φ (s + 1)).card    let c := (simple_graph_endpoint_sum_edges G φ (2 * s)).card    a + b + c = G.edgeFinset.card := by  intro a b c  change (simple_graph_endpoint_sum_edges G φ 2).card +    (simple_graph_endpoint_sum_edges G φ (s + 1)).card +    (simple_graph_endpoint_sum_edges G φ (2 * s)).card = G.edgeFinset.card  simp only [simple_graph_endpoint_sum_edges]  apply admissibility_lemma_edge_partition_three_fibers G.edgeFinset    (fun e => Sym2.lift ⟨fun u v => φ u + φ v, fun _ _ => add_comm _ _⟩ e)    2 (s + 1) (2 * s)  · omega  · omega  · omega  · intro e he    refine Sym2.inductionOn e fun u v => ?_    dsimp    rcases hφ u with hu | hu <;> rcases hφ v with hv | hv    · left; rw [hu, hv]    · right; left; rw [hu, hv, add_comm]    · right; left; rw [hu, hv]    · right; right; rw [hu, hv, two_mul]
See it in the graphDiscuss this resultChallenge it