simple_graph_multi_radio_number_top
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
- simple_graph_multi_radio_numberThe (m,k)-radio number lambda_k^m(G): the least span of an (m,k)-radio labeling of G.
- multi_label_span_ge_of_radio_labeling_topLower bound: every (m,k)-radio labeling of the complete graph K_n has span at least k(mn - 1).
- exists_radio_labeling_top_span_eqUpper bound: the labeling f(v_i) = {ik, (n+i)k, ..., ((m-1)n+i)k} is an (m,k)-radio labeling of K_n of span k(mn - 1).
- 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…
- multi_label_spanThe span of a multi-labeling: the largest label used minus the smallest (written as the largest difference b - a over all pairs of labels).
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.
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).
uses
exists_radio_labeling_top_span_eqhave _ := hm dsimp [simple_graph_multi_radio_number] rcases exists_radio_labeling_top_span_eq n m k hn hk with ⟨f, hf, hspan⟩
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).
uses
le_antisymm,Nat.sInf_leapply 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
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.
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).
- The hypothesis `hm : 1 ≤ m` is placed into the local context at line 3 (`have _ := hm`), but is not needed by the subsequent helper lemmas `exists_radio_labeling_top_span_eq` and `multi_label_span_ge_of_radio_labeling_top`.
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.
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