AFTD Auto-Formalizing Theoretical Domains

exists_multi_radio_labeling_path

theoremverified

For all n, m, k there is an (m,k)-radio labeling of the path P_n: on vertex v put the m labels (k+1)*(m*v + a) for a < m.

Statement

theorem exists_multi_radio_labeling_path (n m k : ℕ) :
    ∃ f : Fin n → Finset ℕ, simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph n) m k f
Source
step towards simple_graph_multi_radio_number_path_three_of_le
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • simple_graph_is_multi_radio_labelingAn (m,k)-radio labeling of G: each vertex gets a set of m nonnegative integer labels, and for any (possibly equal) vertices x, y and…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

The proof, explained

An $(m,k)$-radio labeling of the path $P_n$ requires assigning each vertex $v$ a set of $m$ labels such that distinct vertex-label pairs satisfy $|a - b| \ge (k+1) - \mathrm{dist}(x, y)$. The proof constructs an explicit labeling by setting $f(v) = \{(k+1)(mv + a) : a \in \{0, \dots, m-1\}\}$, where $mv + a$ uniquely identifies each vertex and label index by uniqueness of quotient and remainder. Because each label is a distinct multiple of $k+1$, any two distinct labels differ by at least $k+1$. Since graph distance is non-negative, $(k+1) - \mathrm{dist}(x, y) \le k+1 \le |a - b|$, satisfying the radio condition everywhere without needing to calculate path distances.

  1. If remainders satisfy $a' < m$ and $b' < m$, and $(x, a') \ne (y, b')$, then $m x + a' \ne m y + b'$.

    We split by trichotomy on $x$ and $y$. If $x < y$, then $x + 1 \le y$, so $m(x + 1) \le m y$; since $a' < m$, we have $m x + a' < m(x + 1) \le m y \le m y + b'$, preventing equality. The case $y < x$ is symmetric. If $x = y$, the assumed inequality $(x, a') \ne (x, b')$ means $a' \ne b'$, so $m x + a' \ne m x + b'$.

    lines 3–11

    uses lt_trichotomy, Nat.mul_le_mul_left

      rcases lt_trichotomy x y with hlt | heq | hgt
      · have : m * (x + 1) ≤ m * y := Nat.mul_le_mul_left m hlt
        nlinarith
      · subst heq
        intro h
        have : a' = b' := by omega
        exact hne (by rw [this])
      · have : m * (y + 1) ≤ m * x := Nat.mul_le_mul_left m hgt
        nlinarith
  2. For natural numbers $k$ and distinct $u \ne v$, the integer absolute difference satisfies $|(k+1)u - (k+1)v| \ge k + 1$.

    After pushing casts from $\mathbb{N}$ to $\mathbb{Z}$, we split by trichotomy on $u$ and $v$. The case $u = v$ is ruled out by the hypothesis $u \ne v$. If $u < v$, then $u + 1 \le v$, so $(k+1)u < (k+1)v$; the absolute value simplifies to $(k+1)v - (k+1)u = (k+1)(v - u) \ge k + 1$. The case $v < u$ is symmetric.

    lines 15–29

    uses lt_trichotomy, abs_of_neg, abs_of_pos

      push_cast
      rcases lt_trichotomy u v with hlt | heq | hgt
      · have : (u : ℤ) < (v : ℤ) := by exact_mod_cast hlt
        have : (k + 1 : ℤ) * (u : ℤ) < (k + 1 : ℤ) * (v : ℤ) := by
          nlinarith
        rw [abs_of_neg (by linarith)]
        have : (u : ℤ) + 1 ≤ (v : ℤ) := by omega
        nlinarith
      · exact (h heq).elim
      · have : (v : ℤ) < (u : ℤ) := by exact_mod_cast hgt
        have : (k + 1 : ℤ) * (v : ℤ) < (k + 1 : ℤ) * (u : ℤ) := by
          nlinarith
        rw [abs_of_pos (by linarith)]
        have : (v : ℤ) + 1 ≤ (u : ℤ) := by omega
        nlinarith
  3. It suffices to verify the cardinality and distance conditions for the candidate labeling $f(v) = \{(k+1)(mv + a) : a < m\}$.

    We instantiate the existential quantifier with the labeling assigning to each vertex $v$ the image of $\{0, \dots, m-1\}$ under $a \mapsto (k+1)(mv + a)$. Unfolding the definition of a multi-radio labeling splits the goal into two parts: checking that each label set has size $m$, and verifying the radio inequality for any distinct vertex-label pairs.

    lines 34–36

      use fun v => (Finset.range m).image (fun a => (k + 1) * (m * v.val + a))
      dsimp [simple_graph_is_multi_radio_labeling]
      constructor
  4. For each vertex $v$, the label set $f(v)$ has cardinality $m$.

    The set $f(v)$ is the image of $\{0, \dots, m-1\}$ under $a \mapsto (k+1)(mv + a)$. Since $k+1 > 0$, multiplying by $k+1$ is injective, and adding $mv$ preserves injectivity. Because the function is injective, the cardinality of the image equals the cardinality of $\{0, \dots, m-1\}$, which is $m$.

    lines 37–41

    uses Finset.card_image_of_injective, Finset.card_range, Nat.eq_of_mul_eq_mul_left, Nat.succ_pos

      · intro v
        rw [Finset.card_image_of_injective, Finset.card_range]
        intro a b h
        have h2 := Nat.eq_of_mul_eq_mul_left (Nat.succ_pos k) h
        omega
  5. Any labels $a \in f(x)$ and $b \in f(y)$ can be expressed as $a = (k+1)(mx + a')$ and $b = (k+1)(my + b')$ with $a', b' < m$.

    Unpacking the definition of $f$ as the image of the range $\{0, \dots, m-1\}$, every element $a \in f(x)$ arises from some remainder $a' < m$ as $a = (k+1)(mx + a')$, and similarly $b = (k+1)(my + b')$ for some $b' < m$.

    lines 42–46

    uses Finset.mem_image, Finset.mem_range

      · intro x y a ha b hb hne
        rw [Finset.mem_image] at ha hb
        rcases ha with ⟨a', ha', rfl⟩
        rcases hb with ⟨b', hb', rfl⟩
        rw [Finset.mem_range] at ha' hb'
  6. If $(x, a) \ne (y, b)$, then the indices $mx + a'$ and $my + b'$ are distinct.

    By the first helper lemma, $mx + a' \ne my + b'$ provided $(x, a') \ne (y, b')$. If instead $(x, a') = (y, b')$, then $x = y$ and $a' = b'$, which would force $a = b$ and hence $(x, a) = (y, b)$, contradicting the hypothesis.

    lines 47–53

    uses exists_multi_radio_labeling_path_helper, Fin.ext, Prod.mk.inj

        have hdiff : m * x.val + a' ≠ m * y.val + b' := by
          apply exists_multi_radio_labeling_path_helper x.val y.val a' b' m ha' hb'
          intro h_eq
          have hxy : x = y := Fin.ext (Prod.mk.inj h_eq).1
          have hab : a' = b' := (Prod.mk.inj h_eq).2
          subst hxy hab
          exact hne rfl
  7. The radio condition $(k+1) - \mathrm{dist}(x, y) \le |a - b|$ holds for all distinct pairs $(x, a) \ne (y, b)$.

    Applying the second helper lemma to the distinct indices $mx + a'$ and $my + b'$ yields $|a - b| \ge k + 1$. Since graph distance is always non-negative ($\mathrm{dist}(x, y) \ge 0$), linear arithmetic gives $(k+1) - \mathrm{dist}(x, y) \le k + 1 \le |a - b|$, concluding the proof.

    lines 54–56

    uses exists_multi_radio_labeling_path_diff_ge

        have hge := exists_multi_radio_labeling_path_diff_ge k (m * x.val + a') (m * y.val + b') hdiff
        have hdist : 0 ≤ ((SimpleGraph.pathGraph n).dist x y : ℤ) := by positivity
        linarith
lt_trichotomy
Every pair of elements in a linear order satisfies $a < b$, $a = b$, or $b < a$.
Nat.mul_le_mul_left
Multiplication on the left by a natural number preserves the $\le$ relation: if $a \le b$, then $c \cdot a \le c \cdot b$.
abs_of_neg
The absolute value of a strictly negative number is its negation: if $a < 0$, then $|a| = -a$.
abs_of_pos
The absolute value of a strictly positive number is itself: if $a > 0$, then $|a| = a$.
Finset.card_image_of_injective
The image of a finite set under an injective function has the same cardinality as the original set.
Finset.card_range
The range $\{0, \dots, n-1\}$ has cardinality $n$.
Nat.eq_of_mul_eq_mul_left
If $n > 0$ and $n \cdot a = n \cdot b$ for natural numbers, then $a = b$.
Nat.succ_pos
For every natural number $n$, $n + 1 > 0$.
Finset.mem_image
An element belongs to the image $f(s)$ if and only if it equals $f(a)$ for some $a \in s$.
Finset.mem_range
A natural number $m$ belongs to the range $\{0, \dots, n-1\}$ if and only if $m < n$.
exists_multi_radio_labeling_path_helper
If remainders satisfy $a' < m$ and $b' < m$, then $(x, a') \ne (y, b')$ implies $m \cdot x + a' \ne m \cdot y + b'$.
Fin.ext
Two elements of $\mathrm{Fin}(n)$ are equal if and only if their underlying natural numbers are equal.
Prod.mk.inj
An equality of pairs $(a, b) = (c, d)$ implies both $a = c$ and $b = d$.
exists_multi_radio_labeling_path_diff_ge
For natural numbers $u \ne v$, the difference between $(k+1)u$ and $(k+1)v$ as integers satisfies $|(k+1)u - (k+1)v| \ge k + 1$.

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

lemma exists_multi_radio_labeling_path_helper (x y a' b' m : ℕ) (ha : a' < m) (hb : b' < m)    (hne : (x, a') ≠ (y, b')) : m * x + a' ≠ m * y + b' := by  rcases lt_trichotomy x y with hlt | heq | hgt  · have : m * (x + 1) ≤ m * y := Nat.mul_le_mul_left m hlt    nlinarith  · subst heq    intro h    have : a' = b' := by omega    exact hne (by rw [this])  · have : m * (y + 1) ≤ m * x := Nat.mul_le_mul_left m hgt    nlinarithlemma exists_multi_radio_labeling_path_diff_ge (k u v : ℕ) (h : u ≠ v) :    (k + 1 : ℤ) ≤ |(((k + 1) * u : ℕ) : ℤ) - (((k + 1) * v : ℕ) : ℤ)| := by  push_cast  rcases lt_trichotomy u v with hlt | heq | hgt  · have : (u : ℤ) < (v : ℤ) := by exact_mod_cast hlt    have : (k + 1 : ℤ) * (u : ℤ) < (k + 1 : ℤ) * (v : ℤ) := by      nlinarith    rw [abs_of_neg (by linarith)]    have : (u : ℤ) + 1 ≤ (v : ℤ) := by omega    nlinarith  · exact (h heq).elim  · have : (v : ℤ) < (u : ℤ) := by exact_mod_cast hgt    have : (k + 1 : ℤ) * (v : ℤ) < (k + 1 : ℤ) * (u : ℤ) := by      nlinarith    rw [abs_of_pos (by linarith)]    have : (v : ℤ) + 1 ≤ (u : ℤ) := by omega    nlinarith/-- Existence witness for the (m,k)-radio labeling predicate on paths; supplies nonemptiness of the set whose infimum is the (m,k)-radio number. -/theorem exists_multi_radio_labeling_path (n m k : ℕ) :    ∃ f : Fin n → Finset ℕ, simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph n) m k f := by  use fun v => (Finset.range m).image (fun a => (k + 1) * (m * v.val + a))  dsimp [simple_graph_is_multi_radio_labeling]  constructor  · intro v    rw [Finset.card_image_of_injective, Finset.card_range]    intro a b h    have h2 := Nat.eq_of_mul_eq_mul_left (Nat.succ_pos k) h    omega  · intro x y a ha b hb hne    rw [Finset.mem_image] at ha hb    rcases ha with ⟨a', ha', rfl⟩    rcases hb with ⟨b', hb', rfl⟩    rw [Finset.mem_range] at ha' hb'    have hdiff : m * x.val + a' ≠ m * y.val + b' := by      apply exists_multi_radio_labeling_path_helper x.val y.val a' b' m ha' hb'      intro h_eq      have hxy : x = y := Fin.ext (Prod.mk.inj h_eq).1      have hab : a' = b' := (Prod.mk.inj h_eq).2      subst hxy hab      exact hne rfl    have hge := exists_multi_radio_labeling_path_diff_ge k (m * x.val + a') (m * y.val + b') hdiff    have hdist : 0 ≤ ((SimpleGraph.pathGraph n).dist x y : ℤ) := by positivity    linarith
See it in the graphDiscuss this resultChallenge it