simple_graph_multi_radio_number_path_mono
The (m,k)-radio number of the path P_n is nondecreasing in n: a labeling of P_{n+1} restricts to one of P_n.
Statement
theorem simple_graph_multi_radio_number_path_mono (n m k : ℕ) (hn : 1 ≤ n) :
simple_graph_multi_radio_number (SimpleGraph.pathGraph n) m k ≤
simple_graph_multi_radio_number (SimpleGraph.pathGraph (n + 1)) m k- Source
- for simple_graph_multi_radio_number_path_three_of_le (OP-384)
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- simple_graph_multi_radio_numberThe (m,k)-radio number lambda_k^m(G): the least span of an (m,k)-radio labeling of G.
- 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).
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
- Used by 2
- simple_graph_multi_radio_number_path_three_of_le_of_forallReduction of the thread goal to one finite statement per m: if no (m,3)-radio labeling of P_{4m+4} has all labels at most 8m - 2, then the…
- simple_graph_multi_radio_number_path_three_one_of_leFor every n >= 8 the (1,3)-radio number of the path P_n is exactly 7: the case m = 1 of the thread's goal (8m - 1 for n >= 4m + 4).
The proof, explained
To prove that the (m,k)-multi-radio number of the path graph P_n is at most that of P_{n+1}, an optimal multi-radio labeling of P_{n+1} is pulled back to P_n via the canonical inclusion Fin.castSucc. Because this embedding preserves adjacency, it does not increase graph distances, ensuring that the pulled-back labeling remains a valid multi-radio labeling on P_n. Since the span of the restricted labeling cannot exceed that of the original labeling, the multi-radio number of P_n—defined as the minimum span among all valid labelings—is bounded above by that of P_{n+1}.
Construct a shortest walk p in P_n between a and b and define the graph embedding hhom from P_n to P_{n+1} via Fin.castSucc.
Because P_n is preconnected, there exists a walk p connecting a and b of length equal to dist_{P_n}(a, b). The vertex map Fin.castSucc preserves adjacency because adjacent vertices in P_n differ in index by 1, which remains unchanged when cast into Fin (n+1).
uses
SimpleGraph.pathGraph_preconnected,SimpleGraph.pathGraph_adjobtain ⟨p, hp⟩ := ((SimpleGraph.pathGraph_preconnected n) a b).exists_walk_length_eq_dist let hhom : SimpleGraph.pathGraph n →g SimpleGraph.pathGraph (n+1) := { toFun := Fin.castSucc map_rel' := by intro x y hxy simpa [SimpleGraph.pathGraph_adj] using hxy }
The distance in P_{n+1} between Fin.castSucc a and Fin.castSucc b is at most their distance in P_n.
Mapping the walk p across the graph homomorphism hhom yields a walk in P_{n+1} between Fin.castSucc a and Fin.castSucc b. The mapped walk has the same length as p, which is dist_{P_n}(a, b). Since the distance in P_{n+1} is bounded by the length of any connecting walk, dist_{P_{n+1}}(Fin.castSucc a, Fin.castSucc b) ≤ dist_{P_n}(a, b).
uses
SimpleGraph.dist_le,SimpleGraph.Walk.map,SimpleGraph.Walk.length_maphave key := SimpleGraph.dist_le (SimpleGraph.Walk.map hhom p) rw [SimpleGraph.Walk.length_map] at key rw [hp] at key exact key
The pulled-back labeling f ∘ φ assigns m labels per vertex, and injectivity of φ preserves distinctness of pairs.
For each vertex v, |(f ∘ φ)(v)| = |f(φ(v))| = m. Given distinct pairs (x, a) ≠ (y, b) with a ∈ f(φ(x)) and b ∈ f(φ(y)), if (φ(x), a) = (φ(y), b) then φ(x) = φ(y) and a = b; by injectivity of φ, x = y, which would contradict (x, a) ≠ (y, b). Hence (φ(x), a) ≠ (φ(y), b).
uses
congrArg,Prod.fst,Prod.sndrefine ⟨fun v => hf.1 (φ v), ?_⟩ intro x y a ha b hb hne have hne' : (φ x, a) ≠ (φ y, b) := by intro h apply hne have h1 : φ x = φ y := congrArg Prod.fst h have h2 : a = b := congrArg Prod.snd h rw [hφ h1, h2]
The pulled-back labeling f ∘ φ satisfies the (m,k)-multi-radio condition on G.
Since (φ(x), a) ≠ (φ(y), b), the multi-radio condition on G' gives k + 1 - dist_{G'}(φ(x), φ(y)) ≤ |a - b|. Combined with the hypothesis dist_{G'}(φ(x), φ(y)) ≤ dist_G(x, y), linear arithmetic over the integers yields k + 1 - dist_G(x, y) ≤ |a - b|.
have h1 := hf.2 (φ x) (φ y) a ha b hb hne' have h2 : ((G'.dist (φ x) (φ y) : ℕ) : ℤ) ≤ ((G.dist x y : ℕ) : ℤ) := by exact_mod_cast hdist x y linarith
The span of f ∘ φ is bounded above by the span of f.
Unfolding the definition of span as a nested supremum of label differences, for any x, y ∈ V the images φ(x), φ(y) lie in the vertex set W. The supremum over the subset φ(V) is bounded above by the supremum over all of W by transitivity and the properties of finite suprema.
uses
Finset.sup_le,le_trans,Finset.le_sup,Finset.mem_univsimp only [multi_label_span] refine Finset.sup_le fun x _ => Finset.sup_le fun y _ => ?_ exact le_trans (Finset.le_sup (s := (Finset.univ : Finset W)) (f := fun y => (f (φ x)).sup fun a => (f y).sup fun b => b - a) (Finset.mem_univ (φ y))) (Finset.le_sup (s := (Finset.univ : Finset W)) (f := fun x => (Finset.univ : Finset W).sup fun y => (f x).sup fun a => (f y).sup fun b => b - a) (Finset.mem_univ (φ x)))
Construct an injective encoding h : V × Fin m → ℕ scaled by k + 1, verifying that each vertex receives m distinct labels.
Using the bijection Fintype.equivFin between V × Fin m and Fin (|V| * m), we obtain an injective map h to ℕ. Each vertex v is assigned {h(v, a) * (k+1) | a ∈ Fin m}. Since k + 1 > 0, multiplication by k + 1 cancels, so the label assignment is injective on Fin m and produces a set of size m.
uses
Fintype.equivFin,Fin.val_injective,Finset.card_image_of_injective,Nat.succ_pos,Nat.mul_right_cancel_iff,congrArg,Prod.sndclassical let h : V × Fin m → ℕ := fun p => (Fintype.equivFin (V × Fin m) p).val have h_inj : Function.Injective h := by intro p q hpq exact (Fintype.equivFin (V × Fin m)).injective (Fin.val_injective hpq) refine ⟨fun v => (Finset.univ : Finset (Fin m)).image (fun a => h (v, a) * (k+1)), ?_, ?_⟩ · intro v rw [Finset.card_image_of_injective _ ?_] simp intro a b hab have hk : 0 < k + 1 := Nat.succ_pos k have h1 : h (v, a) = h (v, b) := (Nat.mul_right_cancel_iff hk).mp hab exact congrArg Prod.snd (h_inj h1)
Distinct pairs (x, a) ≠ (y, b) have distinct encodings h(x, a') ≠ h(y, b'), giving a non-zero difference in ℤ.
Writing a = h(x, a') * (k+1) and b = h(y, b') * (k+1), if h(x, a') = h(y, b') then injectivity of h implies (x, a') = (y, b'), so (x, a) = (y, b), a contradiction. Hence h(x, a') ≠ h(y, b'), which means their difference as integers is non-zero.
uses
Finset.mem_image,Finset.mem_univ,true_and,Prod.mk.injEq· intro x y a ha b hb hne simp only [Finset.mem_image, Finset.mem_univ, true_and] at ha hb obtain ⟨a', ha'⟩ := ha obtain ⟨b', hb'⟩ := hb have hneN : h (x, a') ≠ h (y, b') := by intro hEq apply hne have hp : (x, a') = (y, b') := h_inj hEq simp only [Prod.mk.injEq] at hp rw [← ha', ← hb', hp.1, hp.2] have hz : ((h (x, a') : ℤ)) - ((h (y, b') : ℤ)) ≠ 0 := by intro hcon apply hneN have : ((h (x, a') : ℤ)) = ((h (y, b') : ℤ)) := by linarith exact_mod_cast this
The constructed labeling satisfies the multi-radio inequality k + 1 - dist_G(x, y) ≤ |a - b|.
Factoring out k + 1, |a - b| = |h(x, a') - h(y, b')| * (k + 1). Because the integer difference is non-zero, its absolute value is at least 1, so |a - b| ≥ 1 * (k + 1) = k + 1. Since dist_G(x, y) ≥ 0, k + 1 - dist_G(x, y) ≤ k + 1 ≤ |a - b|.
uses
abs_mul,abs_of_nonneg,Int.one_le_abs,mul_le_mul_of_nonneg_righthave step1 : ((a : ℤ) - (b : ℤ)) = (((h (x, a') : ℤ)) - ((h (y, b') : ℤ))) * ((k : ℤ) + 1) := by rw [← ha', ← hb'] push_cast ring have habs : |((a : ℤ) - (b : ℤ))| = |(((h (x, a') : ℤ)) - ((h (y, b') : ℤ)))| * ((k : ℤ) + 1) := by rw [step1, abs_mul, abs_of_nonneg (by positivity : (0:ℤ) ≤ (k : ℤ) + 1)] have hone : (1:ℤ) ≤ |(((h (x, a') : ℤ)) - ((h (y, b') : ℤ)))| := Int.one_le_abs hz rw [habs] calc ((k : ℤ) + 1 - ((G.dist x y : ℕ) : ℤ)) ≤ (k : ℤ) + 1 := by have : (0:ℤ) ≤ ((G.dist x y : ℕ) : ℤ) := by positivity linarith _ = 1 * ((k : ℤ) + 1) := by ring _ ≤ |(((h (x, a') : ℤ)) - ((h (y, b') : ℤ)))| * ((k : ℤ) + 1) := by apply mul_le_mul_of_nonneg_right hone (by positivity)
There exists an optimal (m,k)-multi-radio labeling f of P_{n+1} achieving the multi-radio number of P_{n+1}.
By the existence lemma, P_{n+1} has at least one (m,k)-multi-radio labeling, so the set of spans of valid labelings is non-empty. By Nat.sInf_mem, this set of natural numbers contains its infimum, so there is a labeling f with span equal to simple_graph_multi_radio_number(P_{n+1}, m, k).
uses
simple_graph_multi_radio_number_path_mono_exists_labeling,Nat.sInf_memclassical have hne : {s : ℕ | ∃ f : Fin (n+1) → Finset ℕ, simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph (n+1)) m k f ∧ multi_label_span f = s}.Nonempty := by obtain ⟨f, hf⟩ := simple_graph_multi_radio_number_path_mono_exists_labeling (SimpleGraph.pathGraph (n+1)) m k exact ⟨_, f, hf, rfl⟩ obtain ⟨f, hf, hspan⟩ := Nat.sInf_mem hne
The pullback of f along Fin.castSucc is a valid (m,k)-multi-radio labeling of P_n.
The map Fin.castSucc is injective, and by the distance lemma, it does not increase graph distances: dist_{P_{n+1}}(Fin.castSucc x, Fin.castSucc y) ≤ dist_{P_n}(x, y). By the composition lemma, pulling back f along Fin.castSucc gives an (m,k)-multi-radio labeling of P_n.
uses
simple_graph_multi_radio_number_path_mono_labeling_comp,Fin.castSucc_injective,simple_graph_multi_radio_number_path_mono_dist_castSucc_lehave hlabel : simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph n) m k (fun v => f (Fin.castSucc v)) := simple_graph_multi_radio_number_path_mono_labeling_comp _ _ m k f Fin.castSucc hf (Fin.castSucc_injective n) (fun x y => simple_graph_multi_radio_number_path_mono_dist_castSucc_le n x y)
The multi-radio number of P_n is at most the multi-radio number of P_{n+1}.
Because the pulled-back labeling on P_n is valid, its span is an upper bound for the infimum simple_graph_multi_radio_number(P_n, m, k). In turn, by the span comparison lemma, the span of the pulled-back labeling is at most the span of f, which equals simple_graph_multi_radio_number(P_{n+1}, m, k). Chaining these inequalities by transitivity establishes monotonicity.
uses
Nat.sInf_le,simple_graph_multi_radio_number_path_mono_span_comp_le,le_trans,le_of_eqhave hmem : multi_label_span (fun v => f (Fin.castSucc v)) ∈ {s : ℕ | ∃ g : Fin n → Finset ℕ, simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph n) m k g ∧ multi_label_span g = s} := ⟨_, hlabel, rfl⟩ have h1 : simple_graph_multi_radio_number (SimpleGraph.pathGraph n) m k ≤ multi_label_span (fun v => f (Fin.castSucc v)) := Nat.sInf_le hmem have h2 : multi_label_span (fun v => f (Fin.castSucc v)) ≤ multi_label_span f := simple_graph_multi_radio_number_path_mono_span_comp_le f Fin.castSucc have h3 : multi_label_span f = simple_graph_multi_radio_number (SimpleGraph.pathGraph (n+1)) m k := hspan exact le_trans h1 (le_trans h2 (le_of_eq h3))
SimpleGraph.pathGraph_preconnected- The path graph P_n is preconnected, meaning any two vertices are connected by a walk.
SimpleGraph.pathGraph_adj- In the path graph P_n, two vertices u and v are adjacent if and only if u + 1 = v or v + 1 = u.
SimpleGraph.dist_le- The graph distance between two vertices is bounded above by the length of any walk between them.
SimpleGraph.Walk.map- A graph homomorphism maps a walk in the source graph to a walk in the target graph.
SimpleGraph.Walk.length_map- Mapping a walk along a graph homomorphism preserves its length.
congrArg- Equal inputs to a function produce equal outputs: if a₁ = a₂, then f(a₁) = f(a₂).
Prod.fst- The first projection of an ordered pair, sending (x, y) to x.
Prod.snd- The second projection of an ordered pair, sending (x, y) to y.
Finset.sup_le- The supremum of a function over a finite set is at most a if every value is at most a.
le_trans- Transitivity of the order relation: if a ≤ b and b ≤ c, then a ≤ c.
Finset.le_sup- The value of a function at any element of a finite set is at most the supremum over that set.
Finset.mem_univ- Every element of a finite type belongs to its universal Finset.
Fintype.equivFin- Any finite type α is in bijection with Fin |α|.
Fin.val_injective- The canonical coercion from Fin n to ℕ is injective.
Finset.card_image_of_injective- The image of a finite set under an injective map has the same cardinality as the original set.
Nat.succ_pos- The successor of any natural number is strictly positive: 0 < n + 1.
Nat.mul_right_cancel_iff- For positive m, multiplication by m can be cancelled: n * m = k * m ↔ n = k.
Finset.mem_image- An element b is in the image of a finite set s under f if and only if b = f(a) for some a ∈ s.
true_and- The conjunction True ∧ p is equivalent to p.
Prod.mk.injEq- Two ordered pairs (a, b) and (c, d) are equal if and only if a = c and b = d.
abs_mul- The absolute value of a product is the product of absolute values: |a * b| = |a| * |b|.
abs_of_nonneg- The absolute value of a non-negative number is the number itself: 0 ≤ a → |a| = a.
Int.one_le_abs- Any non-zero integer has absolute value at least 1: z ≠ 0 → 1 ≤ |z|.
mul_le_mul_of_nonneg_right- Multiplying an inequality b ≤ c on the right by a non-negative number a ≥ 0 yields b * a ≤ c * a.
simple_graph_multi_radio_number_path_mono_exists_labeling- Every finite simple graph admits at least one (m,k)-multi-radio labeling.
Nat.sInf_mem- Every non-empty set of natural numbers contains its infimum (minimum).
simple_graph_multi_radio_number_path_mono_labeling_comp- Pulling back an (m,k)-multi-radio labeling along an injective map that does not increase graph distance yields a valid (m,k)-multi-radio labeling.
Fin.castSucc_injective- The canonical embedding Fin.castSucc : Fin n → Fin (n + 1) is injective.
simple_graph_multi_radio_number_path_mono_dist_castSucc_le- The distance in P_{n+1} between Fin.castSucc a and Fin.castSucc b is at most the distance between a and b in P_n.
Nat.sInf_le- The infimum of a set of natural numbers is less than or equal to any element in the set.
simple_graph_multi_radio_number_path_mono_span_comp_le- The span of a pulled-back labeling f ∘ φ is at most the span of f.
le_of_eq- Equality implies weak inequality: a = b → a ≤ b.
- The existence lemma simple_graph_multi_radio_number_path_mono_exists_labeling constructs an explicit labeling with labels spaced out by multiples of k + 1 solely to prove that the set of labeling spans is non-empty, so that the minimum span exists via Nat.sInf_mem.
- The graph distance comparison between P_n and P_{n+1} is established by viewing the canonical inclusion Fin.castSucc as a graph homomorphism and pushing forward a shortest walk.
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.
lemma simple_graph_multi_radio_number_path_mono_dist_castSucc_le (n : ℕ) (a b : Fin n) : (SimpleGraph.pathGraph (n+1)).dist (Fin.castSucc a) (Fin.castSucc b) ≤ (SimpleGraph.pathGraph n).dist a b := by obtain ⟨p, hp⟩ := ((SimpleGraph.pathGraph_preconnected n) a b).exists_walk_length_eq_dist let hhom : SimpleGraph.pathGraph n →g SimpleGraph.pathGraph (n+1) := { toFun := Fin.castSucc map_rel' := by intro x y hxy simpa [SimpleGraph.pathGraph_adj] using hxy } have key := SimpleGraph.dist_le (SimpleGraph.Walk.map hhom p) rw [SimpleGraph.Walk.length_map] at key rw [hp] at key exact keylemma simple_graph_multi_radio_number_path_mono_labeling_comp {V W : Type*} (G : SimpleGraph V) (G' : SimpleGraph W) (m k : ℕ) (f : W → Finset ℕ) (φ : V → W) (hf : simple_graph_is_multi_radio_labeling G' m k f) (hφ : Function.Injective φ) (hdist : ∀ x y, G'.dist (φ x) (φ y) ≤ G.dist x y) : simple_graph_is_multi_radio_labeling G m k (fun v => f (φ v)) := by refine ⟨fun v => hf.1 (φ v), ?_⟩ intro x y a ha b hb hne have hne' : (φ x, a) ≠ (φ y, b) := by intro h apply hne have h1 : φ x = φ y := congrArg Prod.fst h have h2 : a = b := congrArg Prod.snd h rw [hφ h1, h2] have h1 := hf.2 (φ x) (φ y) a ha b hb hne' have h2 : ((G'.dist (φ x) (φ y) : ℕ) : ℤ) ≤ ((G.dist x y : ℕ) : ℤ) := by exact_mod_cast hdist x y linarithlemma simple_graph_multi_radio_number_path_mono_span_comp_le {V W : Type*} [Fintype V] [Fintype W] (f : W → Finset ℕ) (φ : V → W) : multi_label_span (fun v => f (φ v)) ≤ multi_label_span f := by simp only [multi_label_span] refine Finset.sup_le fun x _ => Finset.sup_le fun y _ => ?_ exact le_trans (Finset.le_sup (s := (Finset.univ : Finset W)) (f := fun y => (f (φ x)).sup fun a => (f y).sup fun b => b - a) (Finset.mem_univ (φ y))) (Finset.le_sup (s := (Finset.univ : Finset W)) (f := fun x => (Finset.univ : Finset W).sup fun y => (f x).sup fun a => (f y).sup fun b => b - a) (Finset.mem_univ (φ x)))lemma simple_graph_multi_radio_number_path_mono_exists_labeling {V : Type*} [Fintype V] (G : SimpleGraph V) (m k : ℕ) : ∃ f : V → Finset ℕ, simple_graph_is_multi_radio_labeling G m k f := by classical let h : V × Fin m → ℕ := fun p => (Fintype.equivFin (V × Fin m) p).val have h_inj : Function.Injective h := by intro p q hpq exact (Fintype.equivFin (V × Fin m)).injective (Fin.val_injective hpq) refine ⟨fun v => (Finset.univ : Finset (Fin m)).image (fun a => h (v, a) * (k+1)), ?_, ?_⟩ · intro v rw [Finset.card_image_of_injective _ ?_] simp intro a b hab have hk : 0 < k + 1 := Nat.succ_pos k have h1 : h (v, a) = h (v, b) := (Nat.mul_right_cancel_iff hk).mp hab exact congrArg Prod.snd (h_inj h1) · intro x y a ha b hb hne simp only [Finset.mem_image, Finset.mem_univ, true_and] at ha hb obtain ⟨a', ha'⟩ := ha obtain ⟨b', hb'⟩ := hb have hneN : h (x, a') ≠ h (y, b') := by intro hEq apply hne have hp : (x, a') = (y, b') := h_inj hEq simp only [Prod.mk.injEq] at hp rw [← ha', ← hb', hp.1, hp.2] have hz : ((h (x, a') : ℤ)) - ((h (y, b') : ℤ)) ≠ 0 := by intro hcon apply hneN have : ((h (x, a') : ℤ)) = ((h (y, b') : ℤ)) := by linarith exact_mod_cast this have step1 : ((a : ℤ) - (b : ℤ)) = (((h (x, a') : ℤ)) - ((h (y, b') : ℤ))) * ((k : ℤ) + 1) := by rw [← ha', ← hb'] push_cast ring have habs : |((a : ℤ) - (b : ℤ))| = |(((h (x, a') : ℤ)) - ((h (y, b') : ℤ)))| * ((k : ℤ) + 1) := by rw [step1, abs_mul, abs_of_nonneg (by positivity : (0:ℤ) ≤ (k : ℤ) + 1)] have hone : (1:ℤ) ≤ |(((h (x, a') : ℤ)) - ((h (y, b') : ℤ)))| := Int.one_le_abs hz rw [habs] calc ((k : ℤ) + 1 - ((G.dist x y : ℕ) : ℤ)) ≤ (k : ℤ) + 1 := by have : (0:ℤ) ≤ ((G.dist x y : ℕ) : ℤ) := by positivity linarith _ = 1 * ((k : ℤ) + 1) := by ring _ ≤ |(((h (x, a') : ℤ)) - ((h (y, b') : ℤ)))| * ((k : ℤ) + 1) := by apply mul_le_mul_of_nonneg_right hone (by positivity)theorem simple_graph_multi_radio_number_path_mono (n m k : ℕ) (hn : 1 ≤ n) : simple_graph_multi_radio_number (SimpleGraph.pathGraph n) m k ≤ simple_graph_multi_radio_number (SimpleGraph.pathGraph (n + 1)) m k := by classical have hne : {s : ℕ | ∃ f : Fin (n+1) → Finset ℕ, simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph (n+1)) m k f ∧ multi_label_span f = s}.Nonempty := by obtain ⟨f, hf⟩ := simple_graph_multi_radio_number_path_mono_exists_labeling (SimpleGraph.pathGraph (n+1)) m k exact ⟨_, f, hf, rfl⟩ obtain ⟨f, hf, hspan⟩ := Nat.sInf_mem hne have hlabel : simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph n) m k (fun v => f (Fin.castSucc v)) := simple_graph_multi_radio_number_path_mono_labeling_comp _ _ m k f Fin.castSucc hf (Fin.castSucc_injective n) (fun x y => simple_graph_multi_radio_number_path_mono_dist_castSucc_le n x y) have hmem : multi_label_span (fun v => f (Fin.castSucc v)) ∈ {s : ℕ | ∃ g : Fin n → Finset ℕ, simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph n) m k g ∧ multi_label_span g = s} := ⟨_, hlabel, rfl⟩ have h1 : simple_graph_multi_radio_number (SimpleGraph.pathGraph n) m k ≤ multi_label_span (fun v => f (Fin.castSucc v)) := Nat.sInf_le hmem have h2 : multi_label_span (fun v => f (Fin.castSucc v)) ≤ multi_label_span f := simple_graph_multi_radio_number_path_mono_span_comp_le f Fin.castSucc have h3 : multi_label_span f = simple_graph_multi_radio_number (SimpleGraph.pathGraph (n+1)) m k := hspan exact le_trans h1 (le_trans h2 (le_of_eq h3))