AFTD Auto-Formalizing Theoretical Domains

admissibility_lemma_necessity

theoremverified

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.

  1. 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}).

    lines 11–13

    uses is_total_edge_irregular_labeling

      obtain ⟨ψ, hψ⟩ := h_ext
      simp only [is_total_edge_irregular_labeling] at hψ
      obtain ⟨hφb, hψb, hinj⟩ := hψ
  2. 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).

    lines 14–22

    uses Nat.add_comm, dif_pos, congrArg

      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'
  3. 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.

    lines 23–39

    uses simple_graph_endpoint_sum_edges, Finset.mem_filter, SimpleGraph.mem_edgeFinset, dif_pos

      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⟩
  4. 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.

    lines 40–52

    uses Finset.card_le_card_of_injOn, Finset.mem_coe, Finset.mem_Icc, Nat.card_Icc

      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
  5. 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.

    lines 53–70

      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)
  6. 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.

    lines 71–91

    uses Finset.disjoint_left, Finset.disjoint_union_left

      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⟩
  7. |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.

    lines 92–100

      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
  8. |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.

    lines 101–113

    uses Finset.mem_union

      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
  9. |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.

    lines 114–126

    uses Finset.mem_union

      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
  10. |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.

    lines 127–139

    uses Finset.mem_union

      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
  11. 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.

    lines 140–146

    uses Finset.card_union_of_disjoint

      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
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

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

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
See it in the graphDiscuss this resultChallenge it