admissibility_lemma_edge_partition
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)|.
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.
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)
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₃.
uses
Finset.disjoint_filterhave 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
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|.
uses
Finset.disjoint_union_left,Finset.card_union_of_disjointhave 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
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|.
uses
Finset.filter_or,Finset.filter_true_of_memhave 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
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.
uses
simple_graph_endpoint_sum_edgesintro 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]
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.
uses
admissibility_lemma_edge_partition_three_fibersapply 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
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}.
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.
- Edges in SimpleGraph are formalised as unordered pairs in the symmetric square Sym2 V, so inspecting an edge's endpoints uses Sym2.inductionOn.
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.
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]