admissibility_lemma_necessity
Let s ≥ 3, let G be a finite simple graph, and let φ : V → ℕ be a vertex labeling such that φ(v) ∈ {1, s} for all v. Let a = |E_2|, b = |E_{s+1}|, and c = |E_{2s}| be the counts of edges with endpoint label sums 2, s + 1, and 2s, respectively. If φ extends to a total edge irregular s-labeling of G, then a ≤ s, b ≤ s, c ≤ s, a + b ≤ 2s - 1, b + c ≤ 2s - 1, and a + b + c ≤ 3s - 2.
Statement
open scoped Classical in theorem admissibility_lemma_necessity {V : Type*} [Fintype V] (G : SimpleGraph V) (s : ℕ) (hs : 3 ≤ s) (φ : V → ℕ) (hφ : ∀ v : V, φ v = 1 ∨ φ v = s) (h_ext : ∃ ψ : G.edgeSet → ℕ, is_total_edge_irregular_labeling G 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 ≤ s ∧ b ≤ s ∧ c ≤ s ∧ a + b ≤ 2 * s - 1 ∧ b + c ≤ 2 * s - 1 ∧ a + b + c ≤ 3 * s - 2
- Source
- arXiv:2611.16338, Lemma 2.1
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_total_edge_irregular_labelingA vertex labeling φ : V → ℕ and an edge labeling ψ : G.edgeSet → ℕ form a total edge irregular s-labeling of a simple graph G if all…
- 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…
- Used by 1
- admissibility_lemma_binary_labelingLet s ≥ 3, let G be a finite simple graph, and let φ : V → ℕ be a vertex labeling such that φ(v) ∈ {1, s} for all v. Let a = |E_2|, b =…
Read back from the Lean
For every finite type V, every simple graph G on V, every natural number s ≥ 3, and every vertex labeling φ : V → ℕ such that every vertex v has φ v = 1 or φ v = s:
If there exists an edge labeling ψ : G.edgeSet → ℕ such that (φ, ψ) is a total edge irregular labeling of G with label bound s (that is:
- every vertex label satisfies 1 ≤ φ v ≤ s,
- every edge label satisfies 1 ≤ ψ e ≤ s, and
- the map sending each edge e = s(u, v) to φ u + φ v + ψ e is injective on G.edgeSet),
then, defining:
- a as the number of edges whose endpoint labels sum to 2,
- b as the number of edges whose endpoint labels sum to s + 1, and
- c as the number of edges whose endpoint labels sum to 2 * s,
the following six inequalities hold:
- a ≤ s,
- b ≤ s,
- c ≤ s,
- a + b ≤ 2 * s - 1,
- b + c ≤ 2 * s - 1, and
- a + b + c ≤ 3 * s - 2.
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 applies the pigeonhole principle to total edge weights. Because (φ, ψ) is a total edge irregular labeling, each edge e receives a distinct total weight f(e) = φ(u) + φ(v) + ψ(e). Since edge labels satisfy 1 ≤ ψ(e) ≤ s, an edge with endpoint label sum r has its total weight restricted to the interval [r + 1, r + s], meaning any set of edges whose weights lie in [lo, hi] can contain at most hi + 1 - lo edges. Applying this bound to A = E₂, B = E_{s+1}, C = E_{2s}, and their disjoint unions A ∪ B, B ∪ C, and A ∪ B ∪ C immediately yields the six required upper bounds.
Extract the edge labeling ψ and its properties from the total edge irregular labeling hypothesis
Unpacking the assumption that φ extends to a total edge irregular s-labeling provides an edge labeling ψ : E(G) → ℕ such that 1 ≤ ψ(e) ≤ s for every edge e, and distinct edges have distinct total weights φ(u) + φ(v) + ψ({u, v}).
uses
is_total_edge_irregular_labelingobtain ⟨ψ, hψ⟩ := h_ext simp only [is_total_edge_irregular_labeling] at hψ obtain ⟨hφb, hψb, hinj⟩ := hψ
Define the total edge weight function f and show it is injective on the edge set of G
We define L({u, v}) = φ(u) + φ(v) on unordered pairs using Sym2.lift (well-defined by commutativity of addition, Nat.add_comm), and set f(e) = L(e) + ψ(e) for edges e ∈ E(G) (and 0 otherwise). On edges of G, f agrees with the total edge weight, so the irregularity condition guarantees that f is injective on E(G).
uses
Nat.add_comm,dif_pos,congrArglet L : Sym2 V → ℕ := Sym2.lift ⟨fun u v => φ u + φ v, fun a b => Nat.add_comm _ _⟩ let f : Sym2 V → ℕ := fun e => if h : e ∈ G.edgeSet then L e + ψ ⟨e, h⟩ else 0 have hinjf : Set.InjOn f (G.edgeSet : Set (Sym2 V)) := by intro e1 he1 e2 he2 heq have h1 : f e1 = L e1 + ψ ⟨e1, he1⟩ := dif_pos he1 have h2 : f e2 = L e2 + ψ ⟨e2, he2⟩ := dif_pos he2 rw [h1, h2] at heq have hinj' := hinj ⟨e1, he1⟩ ⟨e2, he2⟩ heq exact congrArg Subtype.val hinj'
For any edge with endpoint sum r, the edge belongs to G and its total weight lies in [r + 1, r + s]
By unfolding simple_graph_endpoint_sum_edges with Finset.mem_filter and SimpleGraph.mem_edgeFinset, any element e with endpoint sum r is indeed an edge of G and satisfies L(e) = r. Since 1 ≤ ψ(e) ≤ s, the total weight f(e) = r + ψ(e) satisfies r + 1 ≤ f(e) ≤ r + s.
uses
simple_graph_endpoint_sum_edges,Finset.mem_filter,SimpleGraph.mem_edgeFinset,dif_poshave hmem : ∀ (r : ℕ) (e : Sym2 V), e ∈ simple_graph_endpoint_sum_edges G φ r → e ∈ G.edgeSet := by intro r e he simp only [simple_graph_endpoint_sum_edges, Finset.mem_filter, SimpleGraph.mem_edgeFinset] at he exact he.1 have hLval : ∀ (r : ℕ) (e : Sym2 V), e ∈ simple_graph_endpoint_sum_edges G φ r → L e = r := by intro r e he simp only [simple_graph_endpoint_sum_edges, Finset.mem_filter, SimpleGraph.mem_edgeFinset] at he exact he.2 have hbdd : ∀ (r : ℕ) (e : Sym2 V), e ∈ simple_graph_endpoint_sum_edges G φ r → r + 1 ≤ f e ∧ f e ≤ r + s := by intro r e he have hee : e ∈ G.edgeSet := hmem r e he have hLe : L e = r := hLval r e he have hfe : f e = L e + ψ ⟨e, hee⟩ := dif_pos hee obtain ⟨h1, h2⟩ := hψb ⟨e, hee⟩ rw [hfe, hLe] exact ⟨by omega, by omega⟩
Any edge subset whose total weights lie in [lo, hi] has cardinality at most hi + 1 - lo
Because f is injective on E(G), restricting f to any edge subset S whose weights fall in [lo, hi] provides an injection into the discrete interval [lo, hi]. By Finset.card_le_card_of_injOn and Nat.card_Icc, the cardinality of S is bounded by the length of the interval, hi + 1 - lo.
uses
Finset.card_le_card_of_injOn,Finset.mem_coe,Finset.mem_Icc,Nat.card_Icchave key2 : ∀ (lo hi : ℕ) (S : Finset (Sym2 V)), (∀ e ∈ S, e ∈ G.edgeSet) → (∀ e ∈ S, lo ≤ f e ∧ f e ≤ hi) → S.card ≤ hi + 1 - lo := by intro lo hi S hmemS hbound calc S.card ≤ (Finset.Icc lo hi).card := by apply Finset.card_le_card_of_injOn f · intro e he simp only [Finset.mem_coe, Finset.mem_Icc] exact hbound e (Finset.mem_coe.mp he) · intro e1 he1 e2 he2 heq exact hinjf (hmemS e1 (Finset.mem_coe.mp he1)) (hmemS e2 (Finset.mem_coe.mp he2)) heq _ = hi + 1 - lo := Nat.card_Icc lo hi
The edge sets A = E₂, B = E_{s+1}, and C = E_{2s} have weights restricted to [3, s + 2], [s + 2, 2s + 1], and [2s + 1, 3s], respectively
Specializing the weight bounds to r = 2, r = s + 1, and r = 2s gives: for e ∈ A, 3 ≤ f(e) ≤ s + 2; for e ∈ B, s + 2 ≤ f(e) ≤ 2s + 1; and for e ∈ C, 2s + 1 ≤ f(e) ≤ 3s. Moreover, all elements of A, B, and C are valid edges of G.
set A := simple_graph_endpoint_sum_edges G φ 2 with hA set B := simple_graph_endpoint_sum_edges G φ (s + 1) with hB set C := simple_graph_endpoint_sum_edges G φ (2 * s) with hC have hA_bdd : ∀ e ∈ A, 3 ≤ f e ∧ f e ≤ s + 2 := by intro e he have := hbdd 2 e (hA ▸ he) omega have hB_bdd : ∀ e ∈ B, s + 2 ≤ f e ∧ f e ≤ 2 * s + 1 := by intro e he have := hbdd (s + 1) e (hB ▸ he) omega have hC_bdd : ∀ e ∈ C, 2 * s + 1 ≤ f e ∧ f e ≤ 3 * s := by intro e he have := hbdd (2 * s) e (hC ▸ he) omega have hA_mem : ∀ e ∈ A, e ∈ G.edgeSet := fun e he => hmem 2 e (hA ▸ he) have hB_mem : ∀ e ∈ B, e ∈ G.edgeSet := fun e he => hmem (s + 1) e (hB ▸ he) have hC_mem : ∀ e ∈ C, e ∈ G.edgeSet := fun e he => hmem (2 * s) e (hC ▸ he)
The sets A, B, and C are pairwise disjoint, and (A ∪ B) is disjoint from C
An edge in both A and B would need endpoint sum equal to both 2 and s + 1, which is impossible since s ≥ 3 implies s + 1 ≥ 4 ≠ 2. Similarly, s + 1 ≠ 2s and 2 ≠ 2s, so A, B, and C are pairwise disjoint by Finset.disjoint_left. By Finset.disjoint_union_left, this also implies (A ∪ B) is disjoint from C.
uses
Finset.disjoint_left,Finset.disjoint_union_lefthave hAB_disj : Disjoint A B := by rw [Finset.disjoint_left] intro e heA heB have h1 : L e = 2 := hLval 2 e (hA ▸ heA) have h2 : L e = s + 1 := hLval (s + 1) e (hB ▸ heB) omega have hBC_disj : Disjoint B C := by rw [Finset.disjoint_left] intro e heB heC have h1 : L e = s + 1 := hLval (s + 1) e (hB ▸ heB) have h2 : L e = 2 * s := hLval (2 * s) e (hC ▸ heC) omega have hAC_disj : Disjoint A C := by rw [Finset.disjoint_left] intro e heA heC have h1 : L e = 2 := hLval 2 e (hA ▸ heA) have h2 : L e = 2 * s := hLval (2 * s) e (hC ▸ heC) omega have hABC_disj : Disjoint (A ∪ B) C := by rw [Finset.disjoint_union_left] exact ⟨hAC_disj, hBC_disj⟩
|A| ≤ s, |B| ≤ s, and |C| ≤ s
Applying the interval bound to each set gives |A| ≤ (s + 2) + 1 - 3 = s, |B| ≤ (2s + 1) + 1 - (s + 2) = s, and |C| ≤ 3s + 1 - (2s + 1) = s.
have hA_card : A.card ≤ s := by have := key2 3 (s + 2) A hA_mem hA_bdd omega have hB_card : B.card ≤ s := by have := key2 (s + 2) (2 * s + 1) B hB_mem hB_bdd omega have hC_card : C.card ≤ s := by have := key2 (2 * s + 1) (3 * s) C hC_mem hC_bdd omega
|A ∪ B| ≤ 2s - 1
For any edge in A ∪ B, its weight is at least 3 and at most 2s + 1. Applying the interval bound to A ∪ B on [3, 2s + 1] gives |A ∪ B| ≤ (2s + 1) + 1 - 3 = 2s - 1.
uses
Finset.mem_unionhave hAB_bdd : ∀ e ∈ A ∪ B, 3 ≤ f e ∧ f e ≤ 2 * s + 1 := by intro e he rw [Finset.mem_union] at he rcases he with heA | heB · have := hA_bdd e heA; omega · have := hB_bdd e heB; omega have hAB_mem : ∀ e ∈ A ∪ B, e ∈ G.edgeSet := by intro e he rw [Finset.mem_union] at he exact he.elim (hA_mem e) (hB_mem e) have hAB_card : (A ∪ B).card ≤ 2 * s - 1 := by have := key2 3 (2 * s + 1) (A ∪ B) hAB_mem hAB_bdd omega
|B ∪ C| ≤ 2s - 1
For any edge in B ∪ C, its weight is at least s + 2 and at most 3s. Applying the interval bound on [s + 2, 3s] gives |B ∪ C| ≤ 3s + 1 - (s + 2) = 2s - 1.
uses
Finset.mem_unionhave hBC_bdd : ∀ e ∈ B ∪ C, s + 2 ≤ f e ∧ f e ≤ 3 * s := by intro e he rw [Finset.mem_union] at he rcases he with heB | heC · have := hB_bdd e heB; omega · have := hC_bdd e heC; omega have hBC_mem : ∀ e ∈ B ∪ C, e ∈ G.edgeSet := by intro e he rw [Finset.mem_union] at he exact he.elim (hB_mem e) (hC_mem e) have hBC_card : (B ∪ C).card ≤ 2 * s - 1 := by have := key2 (s + 2) (3 * s) (B ∪ C) hBC_mem hBC_bdd omega
|A ∪ B ∪ C| ≤ 3s - 2
For any edge in A ∪ B ∪ C, its weight is between 3 and 3s. Applying the interval bound on [3, 3s] gives |A ∪ B ∪ C| ≤ 3s + 1 - 3 = 3s - 2.
uses
Finset.mem_unionhave hABC_bdd : ∀ e ∈ A ∪ B ∪ C, 3 ≤ f e ∧ f e ≤ 3 * s := by intro e he rw [Finset.mem_union] at he rcases he with heAB | heC · have := hAB_bdd e heAB; omega · have := hC_bdd e heC; omega have hABC_mem : ∀ e ∈ A ∪ B ∪ C, e ∈ G.edgeSet := by intro e he rw [Finset.mem_union] at he exact he.elim (hAB_mem e) (hC_mem e) have hABC_card : (A ∪ B ∪ C).card ≤ 3 * s - 2 := by have := key2 3 (3 * s) (A ∪ B ∪ C) hABC_mem hABC_bdd omega
All six inequalities hold: a ≤ s, b ≤ s, c ≤ s, a + b ≤ 2s - 1, b + c ≤ 2s - 1, and a + b + c ≤ 3s - 2
The individual bounds on a, b, c were already proved. Because A, B, and C are pairwise disjoint, Finset.card_union_of_disjoint shows that a + b = |A ∪ B| ≤ 2s - 1, b + c = |B ∪ C| ≤ 2s - 1, and a + b + c = |A ∪ B ∪ C| ≤ 3s - 2.
uses
Finset.card_union_of_disjointdsimp only refine ⟨hA_card, hB_card, hC_card, ?_, ?_, ?_⟩ · rw [← Finset.card_union_of_disjoint hAB_disj]; exact hAB_card · rw [← Finset.card_union_of_disjoint hBC_disj]; exact hBC_card · have hcab : (A ∪ B ∪ C).card = A.card + B.card + C.card := by rw [Finset.card_union_of_disjoint hABC_disj, Finset.card_union_of_disjoint hAB_disj] rw [← hcab]; exact hABC_card
is_total_edge_irregular_labeling- an irregular total labeling assigns labels in {1, ..., s} to vertices and edges such that the total weight of each edge (the edge label plus its two endpoint labels) is distinct
Nat.add_comm- addition on natural numbers is commutative: n + m = m + n
dif_pos- dependent if-then-else evaluates to its 'then' branch when the condition is true
congrArg- equality is preserved under applying a function: if x = y, then f(x) = f(y)
simple_graph_endpoint_sum_edges- the finite set of edges of G whose endpoint labels under φ sum to r
Finset.mem_filter- an element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the filtering predicate
SimpleGraph.mem_edgeFinset- an edge belongs to the edge finset of a graph if and only if it belongs to the graph's edge set
Finset.card_le_card_of_injOn- if a function maps a finite set s into a finite set t injectively, then |s| ≤ |t|
Finset.mem_coe- membership of an element in a finset regarded as a set is equivalent to membership in the finset
Finset.mem_Icc- an element x belongs to the closed integer interval [a, b] if and only if a ≤ x ≤ b
Nat.card_Icc- the number of integers in the closed interval [a, b] is b + 1 - a
Finset.disjoint_left- two finsets are disjoint if and only if no element of the first belongs to the second
Finset.disjoint_union_left- the union s ∪ t is disjoint from u if and only if both s and t are disjoint from u
Finset.mem_union- an element belongs to s ∪ t if and only if it belongs to s or to t
Finset.card_union_of_disjoint- if two finsets are disjoint, the cardinality of their union is the sum of their cardinalities
- The hypothesis `hφ` stating that vertex labels take values in {1, s} is not used in this proof; the six inequalities hold for any subsets of edges with endpoint sums 2, s+1, and 2s under a total edge irregular labeling.
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.
open scoped Classical in/-- Necessity direction of the admissibility lemma for binary vertex labelings. -/theorem admissibility_lemma_necessity {V : Type*} [Fintype V] (G : SimpleGraph V) (s : ℕ) (hs : 3 ≤ s) (φ : V → ℕ) (hφ : ∀ v : V, φ v = 1 ∨ φ v = s) (h_ext : ∃ ψ : G.edgeSet → ℕ, is_total_edge_irregular_labeling G 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 ≤ s ∧ b ≤ s ∧ c ≤ s ∧ a + b ≤ 2 * s - 1 ∧ b + c ≤ 2 * s - 1 ∧ a + b + c ≤ 3 * s - 2 := by obtain ⟨ψ, hψ⟩ := h_ext simp only [is_total_edge_irregular_labeling] at hψ obtain ⟨hφb, hψb, hinj⟩ := hψ let L : Sym2 V → ℕ := Sym2.lift ⟨fun u v => φ u + φ v, fun a b => Nat.add_comm _ _⟩ let f : Sym2 V → ℕ := fun e => if h : e ∈ G.edgeSet then L e + ψ ⟨e, h⟩ else 0 have hinjf : Set.InjOn f (G.edgeSet : Set (Sym2 V)) := by intro e1 he1 e2 he2 heq have h1 : f e1 = L e1 + ψ ⟨e1, he1⟩ := dif_pos he1 have h2 : f e2 = L e2 + ψ ⟨e2, he2⟩ := dif_pos he2 rw [h1, h2] at heq have hinj' := hinj ⟨e1, he1⟩ ⟨e2, he2⟩ heq exact congrArg Subtype.val hinj' have hmem : ∀ (r : ℕ) (e : Sym2 V), e ∈ simple_graph_endpoint_sum_edges G φ r → e ∈ G.edgeSet := by intro r e he simp only [simple_graph_endpoint_sum_edges, Finset.mem_filter, SimpleGraph.mem_edgeFinset] at he exact he.1 have hLval : ∀ (r : ℕ) (e : Sym2 V), e ∈ simple_graph_endpoint_sum_edges G φ r → L e = r := by intro r e he simp only [simple_graph_endpoint_sum_edges, Finset.mem_filter, SimpleGraph.mem_edgeFinset] at he exact he.2 have hbdd : ∀ (r : ℕ) (e : Sym2 V), e ∈ simple_graph_endpoint_sum_edges G φ r → r + 1 ≤ f e ∧ f e ≤ r + s := by intro r e he have hee : e ∈ G.edgeSet := hmem r e he have hLe : L e = r := hLval r e he have hfe : f e = L e + ψ ⟨e, hee⟩ := dif_pos hee obtain ⟨h1, h2⟩ := hψb ⟨e, hee⟩ rw [hfe, hLe] exact ⟨by omega, by omega⟩ have key2 : ∀ (lo hi : ℕ) (S : Finset (Sym2 V)), (∀ e ∈ S, e ∈ G.edgeSet) → (∀ e ∈ S, lo ≤ f e ∧ f e ≤ hi) → S.card ≤ hi + 1 - lo := by intro lo hi S hmemS hbound calc S.card ≤ (Finset.Icc lo hi).card := by apply Finset.card_le_card_of_injOn f · intro e he simp only [Finset.mem_coe, Finset.mem_Icc] exact hbound e (Finset.mem_coe.mp he) · intro e1 he1 e2 he2 heq exact hinjf (hmemS e1 (Finset.mem_coe.mp he1)) (hmemS e2 (Finset.mem_coe.mp he2)) heq _ = hi + 1 - lo := Nat.card_Icc lo hi set A := simple_graph_endpoint_sum_edges G φ 2 with hA set B := simple_graph_endpoint_sum_edges G φ (s + 1) with hB set C := simple_graph_endpoint_sum_edges G φ (2 * s) with hC have hA_bdd : ∀ e ∈ A, 3 ≤ f e ∧ f e ≤ s + 2 := by intro e he have := hbdd 2 e (hA ▸ he) omega have hB_bdd : ∀ e ∈ B, s + 2 ≤ f e ∧ f e ≤ 2 * s + 1 := by intro e he have := hbdd (s + 1) e (hB ▸ he) omega have hC_bdd : ∀ e ∈ C, 2 * s + 1 ≤ f e ∧ f e ≤ 3 * s := by intro e he have := hbdd (2 * s) e (hC ▸ he) omega have hA_mem : ∀ e ∈ A, e ∈ G.edgeSet := fun e he => hmem 2 e (hA ▸ he) have hB_mem : ∀ e ∈ B, e ∈ G.edgeSet := fun e he => hmem (s + 1) e (hB ▸ he) have hC_mem : ∀ e ∈ C, e ∈ G.edgeSet := fun e he => hmem (2 * s) e (hC ▸ he) have hAB_disj : Disjoint A B := by rw [Finset.disjoint_left] intro e heA heB have h1 : L e = 2 := hLval 2 e (hA ▸ heA) have h2 : L e = s + 1 := hLval (s + 1) e (hB ▸ heB) omega have hBC_disj : Disjoint B C := by rw [Finset.disjoint_left] intro e heB heC have h1 : L e = s + 1 := hLval (s + 1) e (hB ▸ heB) have h2 : L e = 2 * s := hLval (2 * s) e (hC ▸ heC) omega have hAC_disj : Disjoint A C := by rw [Finset.disjoint_left] intro e heA heC have h1 : L e = 2 := hLval 2 e (hA ▸ heA) have h2 : L e = 2 * s := hLval (2 * s) e (hC ▸ heC) omega have hABC_disj : Disjoint (A ∪ B) C := by rw [Finset.disjoint_union_left] exact ⟨hAC_disj, hBC_disj⟩ have hA_card : A.card ≤ s := by have := key2 3 (s + 2) A hA_mem hA_bdd omega have hB_card : B.card ≤ s := by have := key2 (s + 2) (2 * s + 1) B hB_mem hB_bdd omega have hC_card : C.card ≤ s := by have := key2 (2 * s + 1) (3 * s) C hC_mem hC_bdd omega have hAB_bdd : ∀ e ∈ A ∪ B, 3 ≤ f e ∧ f e ≤ 2 * s + 1 := by intro e he rw [Finset.mem_union] at he rcases he with heA | heB · have := hA_bdd e heA; omega · have := hB_bdd e heB; omega have hAB_mem : ∀ e ∈ A ∪ B, e ∈ G.edgeSet := by intro e he rw [Finset.mem_union] at he exact he.elim (hA_mem e) (hB_mem e) have hAB_card : (A ∪ B).card ≤ 2 * s - 1 := by have := key2 3 (2 * s + 1) (A ∪ B) hAB_mem hAB_bdd omega have hBC_bdd : ∀ e ∈ B ∪ C, s + 2 ≤ f e ∧ f e ≤ 3 * s := by intro e he rw [Finset.mem_union] at he rcases he with heB | heC · have := hB_bdd e heB; omega · have := hC_bdd e heC; omega have hBC_mem : ∀ e ∈ B ∪ C, e ∈ G.edgeSet := by intro e he rw [Finset.mem_union] at he exact he.elim (hB_mem e) (hC_mem e) have hBC_card : (B ∪ C).card ≤ 2 * s - 1 := by have := key2 (s + 2) (3 * s) (B ∪ C) hBC_mem hBC_bdd omega have hABC_bdd : ∀ e ∈ A ∪ B ∪ C, 3 ≤ f e ∧ f e ≤ 3 * s := by intro e he rw [Finset.mem_union] at he rcases he with heAB | heC · have := hAB_bdd e heAB; omega · have := hC_bdd e heC; omega have hABC_mem : ∀ e ∈ A ∪ B ∪ C, e ∈ G.edgeSet := by intro e he rw [Finset.mem_union] at he exact he.elim (hAB_mem e) (hC_mem e) have hABC_card : (A ∪ B ∪ C).card ≤ 3 * s - 2 := by have := key2 3 (3 * s) (A ∪ B ∪ C) hABC_mem hABC_bdd omega dsimp only refine ⟨hA_card, hB_card, hC_card, ?_, ?_, ?_⟩ · rw [← Finset.card_union_of_disjoint hAB_disj]; exact hAB_card · rw [← Finset.card_union_of_disjoint hBC_disj]; exact hBC_card · have hcab : (A ∪ B ∪ C).card = A.card + B.card + C.card := by rw [Finset.card_union_of_disjoint hABC_disj, Finset.card_union_of_disjoint hAB_disj] rw [← hcab]; exact hABC_card