AFTD Auto-Formalizing Theoretical Domains

simple_graph_multi_radio_number_top

theoremverifiedformalization

For n >= 2, k >= 1 and m >= 1, the (m,k)-radio number of the complete graph K_n is k(mn - 1).

Statement

theorem simple_graph_multi_radio_number_top (n m k : ℕ) (hn : 2 ≤ n) (hk : 1 ≤ k) (hm : 1 ≤ m) :
    simple_graph_multi_radio_number (⊤ : SimpleGraph (Fin n)) m k = k * (m * n - 1)
Formalizes
arXiv:2610.25863 (On Multi-label radio Labelings of Graphs), Proposition 2.3
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

The proof, explained

The (m, k)-radio number of a graph is defined as the infimum of the spans of all valid (m, k)-multi-radio labelings. The theorem computes this value for the complete graph K_n by antisymmetry. An explicit construction provides a labeling with span exactly k(mn - 1) for the upper bound, while a general lower-bound theorem proves that no valid labeling on K_n can have a smaller span.

  1. There exists a valid (m, k)-multi-radio labeling f of the complete graph K_n with span k(mn - 1).

    Unfolding the definition of `simple_graph_multi_radio_number`, the radio number is defined as the infimum of the spans of all valid (m, k)-multi-radio labelings. Lemma `exists_radio_labeling_top_span_eq` provides an explicit labeling f whose span is exactly k(mn - 1).

    lines 3–5

    uses exists_radio_labeling_top_span_eq

      have _ := hm
      dsimp [simple_graph_multi_radio_number]
      rcases exists_radio_labeling_top_span_eq n m k hn hk with ⟨f, hf, hspan⟩
  2. The (m, k)-radio number of K_n is at most k(mn - 1).

    By antisymmetry (`le_antisymm`), equality reduces to proving the upper and lower bounds. For the upper bound, the labeling f shows that k(mn - 1) is in the set of valid labeling spans. By `Nat.sInf_le`, the infimum of a set of natural numbers is at most any of its elements, so the radio number is at most multi_label_span f = k(mn - 1).

    lines 6–10

    uses le_antisymm, Nat.sInf_le

      apply le_antisymm
      · have hmem : multi_label_span f ∈ {s | ∃ f, simple_graph_is_multi_radio_labeling (⊤ : SimpleGraph (Fin n)) m k f ∧ multi_label_span f = s} :=
          ⟨f, hf, rfl⟩
        have hle := Nat.sInf_le hmem
        rwa [hspan] at hle
  3. The (m, k)-radio number of K_n is at least k(mn - 1), concluding the equality.

    By `le_csInf`, a value is bounded above by the infimum of a set if the set is nonempty and the value is a lower bound for every element. The set of spans is nonempty because it contains the span of f. Furthermore, any element b in the set is the span of some valid labeling g; by `multi_label_span_ge_of_radio_labeling_top`, every valid labeling has span at least k(mn - 1). This establishes the lower bound and finishes the proof.

    lines 11–14

    uses le_csInf, multi_label_span_ge_of_radio_labeling_top

      · apply le_csInf
        · exact ⟨multi_label_span f, f, hf, rfl⟩
        · rintro b ⟨g, hg, rfl⟩
          exact multi_label_span_ge_of_radio_labeling_top n m k g hg
exists_radio_labeling_top_span_eq
There exists an (m,k)-multi-radio labeling on the complete graph K_n whose span is exactly k(mn - 1).
le_antisymm
If a ≤ b and b ≤ a in a partial order, then a = b.
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any element of that set.
le_csInf
In a conditionally complete lattice, if a set s is nonempty and a is a lower bound for all elements of s, then a ≤ sInf s.
multi_label_span_ge_of_radio_labeling_top
Every valid (m,k)-multi-radio labeling of the complete graph K_n has span at least k(mn - 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

theorem simple_graph_multi_radio_number_top (n m k : ℕ) (hn : 2 ≤ n) (hk : 1 ≤ k) (hm : 1 ≤ m) :    simple_graph_multi_radio_number (⊤ : SimpleGraph (Fin n)) m k = k * (m * n - 1) := by  have _ := hm  dsimp [simple_graph_multi_radio_number]  rcases exists_radio_labeling_top_span_eq n m k hn hk with ⟨f, hf, hspan⟩  apply le_antisymm  · have hmem : multi_label_span f ∈ {s | ∃ f, simple_graph_is_multi_radio_labeling (⊤ : SimpleGraph (Fin n)) m k f ∧ multi_label_span f = s} :=      ⟨f, hf, rfl⟩    have hle := Nat.sInf_le hmem    rwa [hspan] at hle  · apply le_csInf    · exact ⟨multi_label_span f, f, hf, rfl⟩    · rintro b ⟨g, hg, rfl⟩      exact multi_label_span_ge_of_radio_labeling_top n m k g hg
See it in the graphDiscuss this resultChallenge it