cubic_total_edge_irregularity_strength_lower_bound
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.
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.
dsimp [total_edge_irregularity_strength]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.
uses
Fintype.equivFin,SimpleGraph.card_edgeSet,Sym2.inductionOn,Fin.exthave 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
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 ψ.
uses
le_csInfapply le_csInf hnonempty intro s hs rcases hs with ⟨hs_pos, φ, ψ, hlabel⟩ rcases hlabel with ⟨hφ, hψ, hirr⟩
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].
uses
add_comm,Finset.mem_Icc,Sym2.inductionOnlet 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
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.
uses
Finset.mem_image,Finset.card_le_card,Finset.card_image_of_injective,Finset.card_univ,Nat.card_Icchave 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
|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.
uses
SimpleGraph.card_edgeSet,SimpleGraph.sum_degrees_eq_twice_card_edges,Finset.sum_congr,Finset.sum_const,Finset.card_univ,smul_eq_mulhave 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.
- The application of `le_csInf` requires verifying that the set of admissible label bounds is nonempty, which is proved by constructing a baseline labeling with all vertex labels equal to 1 and edges numbered from 1 to |E|.
- The final deduction of `|V| / 2 + 1 ≤ s` from `2 * |E| = 3 * |V|` and `|E| ≤ 3 * s + 1 - 3` is discharged automatically by `omega` using integer division arithmetic.
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/-- 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