AFTD Auto-Formalizing Theoretical Domains

admissibility_lemma_binary_labeling

theoremverifiedformalization

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, where E_r is the set of edges whose endpoint labels sum to r. Then φ extends to a total edge irregular s-labeling of G if and only if 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_binary_labeling {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
    (∃ ψ : G.edgeSet → ℕ, is_total_edge_irregular_labeling G s φ ψ) ↔
      (a ≤ s ∧ b ≤ s ∧ c ≤ s ∧ a + b ≤ 2 * s - 1 ∧ b + c ≤ 2 * s - 1 ∧ a + b + c ≤ 3 * s - 2)
Formalizes
arXiv:2611.16338, Lemma 2.1
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
  • admissibility_lemma_necessityLet 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 =…
  • admissibility_lemma_sufficiencyLet 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

Let $V$ be a finite type, $G$ be a simple graph on $V$, $s$ be a natural number with $3 \le s$, and $\phi : V \to \mathbb{N}$ be a vertex labeling such that for every vertex $v \in V$, $\phi(v) = 1$ or $\phi(v) = s$. Define: - $a$ to be the number of edges of $G$ whose endpoints' labels under $\phi$ sum to $2$, - $b$ to be the number of edges of $G$ whose endpoints' labels under $\phi$ sum to $s + 1$, - $c$ to be the number of edges of $G$ whose endpoints' labels under $\phi$ sum to $2s$. The theorem asserts that there exists an edge labeling $\psi : G.\text{edgeSet} \to \mathbb{N}$ such that $(\phi, \psi)$ is a total edge irregular labeling of $G$ with weight bound $s$ (i.e., every vertex label is between $1$ and $s$, every edge label is between $1$ and $s$, and the total edge weight—the sum of the edge label and its two endpoint labels—is distinct for all edges) if and only if all of the following six inequalities hold: 1. $a \le s$ 2. $b \le s$ 3. $c \le s$ 4. $a + b \le 2s - 1$ 5. $b + c \le 2s - 1$ 6. $a + b + c \le 3s - 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 equivalence is established by combining its two directions, which are proved as separate lemmas. The forward direction (necessity) shows that any total edge irregular s-labeling extending φ must satisfy the six counting inequalities on the edge sets E₂, E_{s+1}, and E_{2s}. The reverse direction (sufficiency) constructs such a labeling whenever these inequalities hold.

  1. The existence of an extending total edge irregular labeling is equivalent to the six linear inequalities on the edge counts a, b, c.

    After introducing the shorthand notation for the edge counts a = |E₂|, b = |E_{s+1}|, and c = |E_{2s}|, the equivalence follows directly by pairing the necessity implication from `admissibility_lemma_necessity` with the sufficiency implication from `admissibility_lemma_sufficiency`.

    lines 11–12

    uses admissibility_lemma_necessity, admissibility_lemma_sufficiency

      intro a b c
      exact ⟨admissibility_lemma_necessity G s hs φ hφ, admissibility_lemma_sufficiency G s hs φ hφ⟩
admissibility_lemma_necessity
If a binary vertex labeling φ : V → {1, s} on a finite simple graph G extends to a total edge irregular s-labeling (with s ≥ 3), then the edge counts a = |E₂|, b = |E_{s+1}|, and c = |E_{2s}| satisfy a ≤ s, b ≤ s, c ≤ s, a + b ≤ 2s - 1, b + c ≤ 2s - 1, and a + b + c ≤ 3s - 2.
admissibility_lemma_sufficiency
If s ≥ 3 and the edge counts a = |E₂|, b = |E_{s+1}|, and c = |E_{2s}| for a binary vertex labeling φ : V → {1, s} satisfy the six admissibility inequalities, then φ extends to a total edge irregular s-labeling of G.

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/-- Admissibility lemma for binary vertex labelings (Lemma 2.1). -/theorem admissibility_lemma_binary_labeling {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    (∃ ψ : G.edgeSet → ℕ, is_total_edge_irregular_labeling G s φ ψ) ↔      (a ≤ s ∧ b ≤ s ∧ c ≤ s ∧ a + b ≤ 2 * s - 1 ∧ b + c ≤ 2 * s - 1 ∧ a + b + c ≤ 3 * s - 2) := by  intro a b c  exact ⟨admissibility_lemma_necessity G s hs φ hφ, admissibility_lemma_sufficiency G s hs φ hφ⟩
See it in the graphDiscuss this resultChallenge it