AFTD Auto-Formalizing Theoretical Domains

cubic_total_edge_irregularity_strength_lower_bound

theoremverified

Every finite simple graph G on a finite type V that is regular of degree 3 satisfies Fintype.card V / 2 + 1 ≤ total_edge_irregularity_strength G.

Statement

open scoped Classical in
theorem cubic_total_edge_irregularity_strength_lower_bound {V : Type*} [Fintype V]
    (G : SimpleGraph V) (hreg : G.IsRegularOfDegree 3) :
    Fintype.card V / 2 + 1 ≤ total_edge_irregularity_strength G
Source
arXiv:2611.16338, Section 1, equation (1)
Verified
16 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…
  • total_edge_irregularity_strengthThe total edge irregularity strength of a simple graph G is the least positive integer s such that G admits a total edge irregular…

Read back from the Lean

For any finite type $V$ and any simple graph $G$ on $V$, if $G$ is 3-regular (every vertex of $G$ has degree 3), then the total edge irregularity strength of $G$ is at least $|V| / 2 + 1$ (using natural number division).

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 establishes the lower bound by expressing the total edge irregularity strength as the infimum over all valid labeling bounds s, reducing the goal to showing that any such s satisfies |V| / 2 + 1 ≤ s. In any valid total edge irregular labeling with bound s, each edge receives an integer weight in [3, 3s], and because the weights must be distinct, the graph has at most 3s - 2 edges. Using the Handshaking Lemma on a 3-regular graph gives 2|E| = 3|V|, which yields 3|V| ≤ 6s - 4, from which integer division implies |V| / 2 + 1 ≤ s.

  1. The goal is to bound the infimum of the set of positive integers admitting a total edge irregular labeling.

    Unfolding the definition of `total_edge_irregularity_strength` expresses it as the infimum (sInf) of the set of integers s > 0 that admit a valid labeling.

    line 6

      dsimp [total_edge_irregularity_strength]
  2. The set of admissible labeling bounds s > 0 is nonempty.

    We construct an explicit irregular labeling by choosing s = max(1, |E|), labeling every vertex with 1, and assigning each edge a distinct label in {1, ..., |E|} using a bijection with `Fin |E|`. Since the vertex labels are constant, distinct edges receive strictly distinct weights.

    lines 7–30

    uses Fintype.equivFin, SimpleGraph.card_edgeSet, Sym2.inductionOn, Fin.ext

      have hnonempty : {s : ℕ | 0 < s ∧ ∃ (φ : V → ℕ) (ψ : G.edgeSet → ℕ), is_total_edge_irregular_labeling G s φ ψ}.Nonempty := by
        let e := Fintype.equivFin G.edgeSet
        let s := max 1 G.edgeFinset.card
        have hs : 0 < s := by omega
        refine ⟨s, hs, fun _ => 1, fun x => (e x).val + 1, ?_⟩
        dsimp [is_total_edge_irregular_labeling]
        refine ⟨?_, ?_, ?_⟩
        · intro v
          omega
        · intro x
          have hlt := (e x).isLt
          have hc : Fintype.card G.edgeSet = G.edgeFinset.card := SimpleGraph.card_edgeSet
          omega
        · intro x y h
          have h1 : Sym2.lift ⟨fun u v => (1 : ℕ) + 1, fun _ _ => rfl⟩ x.val = 2 := by
            induction x.val using Sym2.inductionOn
            rfl
          have h2 : Sym2.lift ⟨fun u v => (1 : ℕ) + 1, fun _ _ => rfl⟩ y.val = 2 := by
            induction y.val using Sym2.inductionOn
            rfl
          rw [h1, h2] at h
          have : (e x).val = (e y).val := by omega
          have : e x = e y := Fin.ext this
          exact e.injective this
  3. It suffices to show |V| / 2 + 1 ≤ s for an arbitrary admissible bound s.

    By `le_csInf`, a lower bound on an infimum of a nonempty set follows from showing that the lower bound holds for every element in the set. We introduce an arbitrary s from the set and unpack its vertex labeling φ and edge labeling ψ.

    lines 31–34

    uses le_csInf

      apply le_csInf hnonempty
      intro s hs
      rcases hs with ⟨hs_pos, φ, ψ, hlabel⟩
      rcases hlabel with ⟨hφ, hψ, hirr⟩
  4. The edge weight function w is injective and maps every edge to an integer in [3, 3 * s].

    The weight of an edge e = {u, v} is defined as w(e) = φ(u) + φ(v) + ψ(e). The irregularity hypothesis directly states that w is injective. Since vertex labels lie in [1, s], the sum of the endpoints satisfies 2 ≤ φ(u) + φ(v) ≤ 2 * s. Adding the edge label ψ(e) ∈ [1, s] places w(e) in the interval [3, 3 * s].

    lines 35–51

    uses add_comm, Finset.mem_Icc, Sym2.inductionOn

      let w : G.edgeSet → ℕ := fun e =>
        Sym2.lift ⟨fun u v => φ u + φ v, fun _ _ => add_comm _ _⟩ e.val + ψ e
      have hw_inj : Function.Injective w := hirr
      have hw_mem : ∀ e : G.edgeSet, w e ∈ Finset.Icc 3 (3 * s) := by
        intro e
        rw [Finset.mem_Icc]
        have hψe := hψ e
        have hφe : 2 ≤ Sym2.lift ⟨fun u v => φ u + φ v, fun _ _ => add_comm _ _⟩ e.val ∧
            Sym2.lift ⟨fun u v => φ u + φ v, fun _ _ => add_comm _ _⟩ e.val ≤ 2 * s := by
          induction e.val using Sym2.inductionOn with
          | hf u v =>
            dsimp
            have hu := hφ u
            have hv := hφ v
            omega
        dsimp [w]
        omega
  5. The number of edges of G satisfies |E| ≤ 3 * s + 1 - 3.

    The image of the edge set under w is a subset of the interval [3, 3 * s]. Since w is injective, the cardinality of the image equals the number of edges |E|. By `Finset.card_le_card` and `Nat.card_Icc`, |E| is bounded above by the size of the interval, which is 3 * s + 1 - 3.

    lines 52–59

    uses Finset.mem_image, Finset.card_le_card, Finset.card_image_of_injective, Finset.card_univ, Nat.card_Icc

      have himage : Finset.univ.image w ⊆ Finset.Icc 3 (3 * s) := by
        intro x hx
        rw [Finset.mem_image] at hx
        rcases hx with ⟨e, -, rfl⟩
        exact hw_mem e
      have hcard_le := Finset.card_le_card himage
      rw [Finset.card_image_of_injective _ hw_inj, Finset.card_univ] at hcard_le
      rw [Nat.card_Icc] at hcard_le
  6. |V| / 2 + 1 ≤ s, concluding the theorem.

    By the Handshaking Lemma, the sum of degrees is 2 * |E|. Because G is 3-regular, every vertex has degree 3, so this sum also equals 3 * |V|, establishing 2 * |E| = 3 * |V|. Combining this with |E| ≤ 3 * s - 2, integer arithmetic implies |V| / 2 + 1 ≤ s.

    lines 60–68

    uses SimpleGraph.card_edgeSet, SimpleGraph.sum_degrees_eq_twice_card_edges, Finset.sum_congr, Finset.sum_const, Finset.card_univ, smul_eq_mul

      have hc : Fintype.card G.edgeSet = G.edgeFinset.card := SimpleGraph.card_edgeSet
      have h1 : ∑ v : V, G.degree v = 2 * G.edgeFinset.card :=
        SimpleGraph.sum_degrees_eq_twice_card_edges G
      have h2 : ∑ v : V, G.degree v = ∑ v : V, 3 := by
        apply Finset.sum_congr rfl
        intro v _
        exact hreg v
      rw [Finset.sum_const, Finset.card_univ, smul_eq_mul] at h2
      omega
Fintype.equivFin
Every finite type α is in bijection with Fin |α|.
SimpleGraph.card_edgeSet
The cardinality of the edge set as a type equals the cardinality of the edge finset.
Sym2.inductionOn
Every element of the symmetric square Sym2 α is an unordered pair s(x, y) of two elements.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
le_csInf
A value a is at most the infimum of a set s in a conditionally complete lattice if s is nonempty and a is a lower bound for s.
add_comm
Addition is commutative: a + b = b + a.
Finset.mem_Icc
An element x is in the closed interval [a, b] if and only if a ≤ x and x ≤ b.
Finset.mem_image
An element b belongs to the image f(s) if and only if b = f(a) for some a ∈ s.
Finset.card_le_card
If s ⊆ t for finsets s and t, then |s| ≤ |t|.
Finset.card_image_of_injective
An injective function preserves the cardinality of a finset under its image.
Finset.card_univ
The cardinality of the universal finset Finset.univ of a finite type α is |α|.
Nat.card_Icc
The number of natural numbers in the closed interval [a, b] is b + 1 - a.
SimpleGraph.sum_degrees_eq_twice_card_edges
In any finite simple graph, the sum of vertex degrees equals twice the number of edges.
Finset.sum_congr
Sums of two functions over the same finset are equal if the functions agree on every element of the set.
Finset.sum_const
The sum of a constant b over a finset s is equal to |s| • b.
smul_eq_mul
Scalar multiplication of natural numbers coincides with ordinary multiplication.

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/-- The total edge irregularity strength of a finite simple cubic graph is at least |V| / 2 + 1. -/theorem cubic_total_edge_irregularity_strength_lower_bound {V : Type*} [Fintype V]    (G : SimpleGraph V) (hreg : G.IsRegularOfDegree 3) :    Fintype.card V / 2 + 1 ≤ total_edge_irregularity_strength G := by  dsimp [total_edge_irregularity_strength]  have hnonempty : {s : ℕ | 0 < s ∧ ∃ (φ : V → ℕ) (ψ : G.edgeSet → ℕ), is_total_edge_irregular_labeling G s φ ψ}.Nonempty := by    let e := Fintype.equivFin G.edgeSet    let s := max 1 G.edgeFinset.card    have hs : 0 < s := by omega    refine ⟨s, hs, fun _ => 1, fun x => (e x).val + 1, ?_⟩    dsimp [is_total_edge_irregular_labeling]    refine ⟨?_, ?_, ?_⟩    · intro v      omega    · intro x      have hlt := (e x).isLt      have hc : Fintype.card G.edgeSet = G.edgeFinset.card := SimpleGraph.card_edgeSet      omega    · intro x y h      have h1 : Sym2.lift ⟨fun u v => (1 : ℕ) + 1, fun _ _ => rfl⟩ x.val = 2 := by        induction x.val using Sym2.inductionOn        rfl      have h2 : Sym2.lift ⟨fun u v => (1 : ℕ) + 1, fun _ _ => rfl⟩ y.val = 2 := by        induction y.val using Sym2.inductionOn        rfl      rw [h1, h2] at h      have : (e x).val = (e y).val := by omega      have : e x = e y := Fin.ext this      exact e.injective this  apply le_csInf hnonempty  intro s hs  rcases hs with ⟨hs_pos, φ, ψ, hlabel⟩  rcases hlabel with ⟨hφ, hψ, hirr⟩  let w : G.edgeSet → ℕ := fun e =>    Sym2.lift ⟨fun u v => φ u + φ v, fun _ _ => add_comm _ _⟩ e.val + ψ e  have hw_inj : Function.Injective w := hirr  have hw_mem : ∀ e : G.edgeSet, w e ∈ Finset.Icc 3 (3 * s) := by    intro e    rw [Finset.mem_Icc]    have hψe := hψ e    have hφe : 2 ≤ Sym2.lift ⟨fun u v => φ u + φ v, fun _ _ => add_comm _ _⟩ e.val ∧        Sym2.lift ⟨fun u v => φ u + φ v, fun _ _ => add_comm _ _⟩ e.val ≤ 2 * s := by      induction e.val using Sym2.inductionOn with      | hf u v =>        dsimp        have hu := hφ u        have hv := hφ v        omega    dsimp [w]    omega  have himage : Finset.univ.image w ⊆ Finset.Icc 3 (3 * s) := by    intro x hx    rw [Finset.mem_image] at hx    rcases hx with ⟨e, -, rfl⟩    exact hw_mem e  have hcard_le := Finset.card_le_card himage  rw [Finset.card_image_of_injective _ hw_inj, Finset.card_univ] at hcard_le  rw [Nat.card_Icc] at hcard_le  have hc : Fintype.card G.edgeSet = G.edgeFinset.card := SimpleGraph.card_edgeSet  have h1 : ∑ v : V, G.degree v = 2 * G.edgeFinset.card :=    SimpleGraph.sum_degrees_eq_twice_card_edges G  have h2 : ∑ v : V, G.degree v = ∑ v : V, 3 := by    apply Finset.sum_congr rfl    intro v _    exact hreg v  rw [Finset.sum_const, Finset.card_univ, smul_eq_mul] at h2  omega
See it in the graphDiscuss this resultChallenge it