simple_graph_multi_radio_number_path_three_one_of_le
For 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).
Statement
theorem simple_graph_multi_radio_number_path_three_one_of_le (n : ℕ) (hn : 8 ≤ n) :
simple_graph_multi_radio_number (SimpleGraph.pathGraph n) 1 3 = 7- Source
- Special case m = 1 of the thread goal simple_graph_multi_radio_number_path_three_of_le (the case k = 3 of Conjecture 1 of arXiv:2610.25863, OP-384). For m = 1 an (m,3)-radio labeling is an L(3,2,1)-labeling, whose value on long paths is known in that literature; this is a base case of the ladder, not a new result.
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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).
- simple_graph_multi_radio_number_path_le_eight_mulFor n, m >= 1 the (m,3)-radio number of the path P_n is at most 8m - 1.
- simple_graph_multi_radio_number_path_monoThe (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.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - path_three_radio_labeling_span_ge_sevenFor n >= 8, every (1,3)-radio labeling of the path P_n has span at least 7; combined with the upper bound 8m-1 at m = 1 this gives that…
- exists_multi_radio_labeling_pathFor 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.
The proof, explained
To determine the (1, 3)-multi-radio number of the path graph P_n for n ≥ 8, the proof sandwiches it between upper and lower bounds. The upper bound 7 follows from simple_graph_multi_radio_number_path_le_eight_mul. For the lower bound, any valid (1, 3)-labeling of P_8 must have span at least 7, because shifting labels so the minimum is 0 would yield eight values in {0, ..., 6} satisfying separation constraints |b_i - b_j| ≥ 4 - |i - j| for 1 ≤ |i - j| ≤ 3, which is refuted computationally by radio_three_one_path_eight_core. Monotonicity of the path radio number under graph inclusion then extends this lower bound from P_8 to all P_n with n ≥ 8, yielding exactly 7.
No sequence of eight labels in {0, ..., 6} can satisfy the required radio separation constraints. automation
The lemma radio_three_one_path_eight_core asserts that eight values b_0, ..., b_7 in {0, ..., 6} cannot simultaneously satisfy |b_i - b_j| ≥ 4 - (j - i) for all 0 ≤ i < j ≤ 7 with j - i ≤ 3. After unfolding the definition of separation path_radio_sep, this finite state space is refuted by direct kernel computation (decide +kernel).
uses
path_radio_sepunfold path_radio_sep decide +kernel
In the path graph P_n, the shortest-path distance between vertex i and vertex i + d is at most d.
The distance bound path_graph_dist_le_add is proved by induction on d. For d = 0, the distance from a vertex to itself is 0. In the inductive step from d to d + 1, the edge between i + d and i + d + 1 has length 1 by SimpleGraph.pathGraph_adj and SimpleGraph.dist_le. Applying the triangle inequality on the connected graph P_n (via SimpleGraph.pathGraph_preconnected) combines the induction hypothesis with this step to bound the total distance by d + 1.
uses
SimpleGraph.pathGraph_adj,SimpleGraph.dist_le,SimpleGraph.pathGraph_preconnectedtheorem path_graph_dist_le_add (n i d : ℕ) (h : i + d < n) : (SimpleGraph.pathGraph n).dist ⟨i, by omega⟩ ⟨i + d, h⟩ ≤ d := by induction d with | zero => simp | succ d ih => have : Nonempty (Fin n) := ⟨⟨i, by omega⟩⟩ have hc : (SimpleGraph.pathGraph n).Connected := ⟨SimpleGraph.pathGraph_preconnected n⟩ have hadj : (SimpleGraph.pathGraph n).Adj ⟨i + d, by omega⟩ ⟨i + (d + 1), h⟩ := by rw [SimpleGraph.pathGraph_adj]; left; simp; omega have h1 : (SimpleGraph.pathGraph n).dist ⟨i + d, by omega⟩ ⟨i + (d + 1), h⟩ ≤ 1 := by have := SimpleGraph.dist_le hadj.toWalk; simpa using this have h2 := ih (by omega) have h3 := hc.dist_triangle (u := ⟨i, by omega⟩) (v := ⟨i + d, by omega⟩) (w := ⟨i + (d + 1), h⟩) omega
For any two vertices x ≤ y in P_n, their graph distance is at most y - x.
Setting d = y - x in path_graph_dist_le_add gives dist(x, x + (y - x)) ≤ y - x. Since x + (y - x) = y as vertices in Fin n (justified by Fin.ext), substituting this equality yields dist(x, y) ≤ y - x.
uses
path_graph_dist_le_add,Fin.exttheorem path_graph_dist_le_sub {n : ℕ} (x y : Fin n) (hxy : x.val ≤ y.val) : (SimpleGraph.pathGraph n).dist x y ≤ y.val - x.val := by have := path_graph_dist_le_add n x.val (y.val - x.val) (by omega) have hy : (⟨x.val + (y.val - x.val), by omega⟩ : Fin n) = y := Fin.ext (by simp; omega) rw [hy] at this simpa using this
Any (1, 3)-multi-radio labeling of P_8 assigns a single integer to each vertex, and these values satisfy |a(x) - a(y)| ≥ 4 - (y - x) for all x < y.
Because m = 1, each label set f(v) has cardinality 1 by Finset.card_eq_one.mp, so f(v) = {a(v)} for some function a : Fin 8 → ℕ. For distinct vertices x < y, the pair (x, a(x)) is distinct from (y, a(y)) (shown using congrArg and Prod.fst), so the radio labeling condition gives 4 - dist(x, y) ≤ |a(x) - a(y)|. Using the distance bound dist(x, y) ≤ y - x from path_graph_dist_le_sub, linear integer arithmetic yields 4 - (y - x) ≤ |a(x) - a(y)|.
uses
Finset.card_eq_one.mp,congrArg,Prod.fst,path_graph_dist_le_subtheorem radio_three_one_path_eight_span_ge (f : Fin 8 → Finset ℕ) (hf : simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph 8) 1 3 f) : 7 ≤ multi_label_span f := by have h1 : ∀ v, ∃ x, f v = {x} := fun v => Finset.card_eq_one.mp (hf.1 v) choose a ha using h1 have hfa : f = fun v => {a v} := funext ha have hsepZ : ∀ x y : Fin 8, x.val < y.val → (3 + 1 : ℤ) - ((y.val - x.val : ℕ) : ℤ) ≤ |(a x : ℤ) - a y| := by intro x y hxy have hne : (x, a x) ≠ (y, a y) := by intro h; have := congrArg Prod.fst h; simp at this; subst this; omega have := hf.2 x y (a x) (by rw [ha x]; simp) (a y) (by rw [ha y]; simp) hne have hd := path_graph_dist_le_sub x y hxy.le push_cast at this ⊢ have : ((SimpleGraph.pathGraph 8).dist x y : ℤ) ≤ ((y.val - x.val : ℕ) : ℤ) := by exact_mod_cast hd linarith
Assuming for contradiction that the span of f is less than 7, the difference between any two labels is at most 6.
Assuming multi_label_span(f) < 7 for contradiction, the difference a(y) - a(x) is bounded above by the definition of multi_label_span. Since each f(v) = {a(v)}, taking suprema over singletons via Finset.sup_singleton and bounding an element by the supremum over Finset.univ via Finset.le_sup and Finset.mem_univ (combined with le_trans) shows that a(y) - a(x) ≤ multi_label_span(f) ≤ 6.
uses
multi_label_span,Finset.sup_singleton,Finset.le_sup,Finset.mem_univ,le_transby_contra hlt push Not at hlt have hspan : ∀ x y : Fin 8, a y - a x ≤ 6 := by intro x y have : a y - a x ≤ multi_label_span f := by rw [hfa]; unfold multi_label_span simp only [Finset.sup_singleton] exact le_trans (Finset.le_sup (f := fun y => a y - a x) (Finset.mem_univ y)) (Finset.le_sup (f := fun x => Finset.univ.sup fun y => a y - a x) (Finset.mem_univ x)) omega
Normalizing the labels produces a sequence of eight values in {0, ..., 6} satisfying the separation conditions, which contradicts the core lemma and shows the span of f is at least 7.
Using Finset.exists_min_image on Finset.univ, choose an index i0 that minimizes a, and define normalized labels b(v) = a(v) - a(i0). Since a(v) - a(i0) ≤ 6, each b(v) < 7. Expanding the integer separation inequality via le_abs shows that b satisfies path_radio_sep (4 - (j - i)) (b(i)) (b(j)) for all i < j ≤ i + 3. Providing these eight values to radio_three_one_path_eight_core produces a contradiction (False), proving that the span must be at least 7.
uses
Finset.exists_min_image,Finset.univ,Finset.mem_univ,le_abs,path_radio_sep,radio_three_one_path_eight_coreobtain ⟨i0, -, hi0⟩ := Finset.exists_min_image Finset.univ a ⟨0, Finset.mem_univ _⟩ set b : Fin 8 → ℕ := fun v => a v - a i0 with hbdef have hb : ∀ v, b v < 7 := fun v => by have := hspan i0 v; simp only [hbdef]; omega have hsep : ∀ i j : Fin 8, i.val < j.val → j.val ≤ i.val + 3 → path_radio_sep (4 - (j.val - i.val)) (b i) (b j) := by intro i j hij hj have h := hsepZ i j hij have hi := hi0 i (Finset.mem_univ _) have hj' := hi0 j (Finset.mem_univ _) unfold path_radio_sep; simp only [hbdef] rw [le_abs] at h omega exact radio_three_one_path_eight_core ⟨b 0, hb 0⟩ ⟨b 1, hb 1⟩ (hsep 0 1 (by decide) (by decide)) ⟨b 2, hb 2⟩ (hsep 0 2 (by decide) (by decide)) (hsep 1 2 (by decide) (by decide)) ⟨b 3, hb 3⟩ (hsep 0 3 (by decide) (by decide)) (hsep 1 3 (by decide) (by decide)) (hsep 2 3 (by decide) (by decide)) ⟨b 4, hb 4⟩ (hsep 1 4 (by decide) (by decide)) (hsep 2 4 (by decide) (by decide)) (hsep 3 4 (by decide) (by decide)) ⟨b 5, hb 5⟩ (hsep 2 5 (by decide) (by decide)) (hsep 3 5 (by decide) (by decide)) (hsep 4 5 (by decide) (by decide)) ⟨b 6, hb 6⟩ (hsep 3 6 (by decide) (by decide)) (hsep 4 6 (by decide) (by decide)) (hsep 5 6 (by decide) (by decide)) ⟨b 7, hb 7⟩ (hsep 4 7 (by decide) (by decide)) (hsep 5 7 (by decide) (by decide)) (hsep 6 7 (by decide) (by decide))
The (1, 3)-multi-radio number of P_n is at most 7 for any n ≥ 8.
Applying the general upper bound theorem simple_graph_multi_radio_number_path_le_eight_mul with m = 1 establishes that the radio number of P_n is at most 8(1) - 1 = 7, using le_rfl for the parameter inequality.
uses
simple_graph_multi_radio_number_path_le_eight_mul,le_rfltheorem simple_graph_multi_radio_number_path_three_one_of_le (n : ℕ) (hn : 8 ≤ n) : simple_graph_multi_radio_number (SimpleGraph.pathGraph n) 1 3 = 7 := by have hup := simple_graph_multi_radio_number_path_le_eight_mul n 1 (by omega) le_rfl
The (1, 3)-multi-radio number of P_8 is at least 7.
By simple_graph_multi_radio_number_path_mono_exists_labeling, there exists at least one valid labeling of P_8, so the set of spans of valid labelings is nonempty. By Nat.sInf_mem, the infimum defining simple_graph_multi_radio_number is attained by some labeling f. Since any labeling has span at least 7 by radio_three_one_path_eight_span_ge, the radio number of P_8 is at least 7.
uses
simple_graph_multi_radio_number_path_mono_exists_labeling,Nat.sInf_mem,simple_graph_multi_radio_number,radio_three_one_path_eight_span_gehave h8 : 7 ≤ simple_graph_multi_radio_number (SimpleGraph.pathGraph 8) 1 3 := by have hne : {s | ∃ f, simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph 8) 1 3 f ∧ multi_label_span f = s}.Nonempty := by obtain ⟨f, hf⟩ := simple_graph_multi_radio_number_path_mono_exists_labeling (SimpleGraph.pathGraph 8) 1 3 exact ⟨_, f, hf, rfl⟩ obtain ⟨f, hf, hs⟩ := Nat.sInf_mem hne unfold simple_graph_multi_radio_number rw [← hs] exact radio_three_one_path_eight_span_ge f hf
By monotonicity, the radio number of P_n is at least 7 for all n ≥ 8, which together with the upper bound shows the radio number is exactly 7.
Induction on d using simple_graph_multi_radio_number_path_mono (combined with le_rfl and le_trans) proves that the radio number of P_{8+d} is at least that of P_8. Given n ≥ 8, Nat.exists_eq_add_of_le writes n = 8 + d. Thus 7 ≤ radio(P_8) ≤ radio(P_n) ≤ 7, so the radio number is exactly 7.
uses
simple_graph_multi_radio_number_path_mono,le_rfl,le_trans,Nat.exists_eq_add_of_lehave hmono : ∀ d, simple_graph_multi_radio_number (SimpleGraph.pathGraph 8) 1 3 ≤ simple_graph_multi_radio_number (SimpleGraph.pathGraph (8 + d)) 1 3 := by intro d induction d with | zero => exact le_rfl | succ d ih => exact le_trans ih (simple_graph_multi_radio_number_path_mono (8 + d) 1 3 (by omega)) obtain ⟨d, rfl⟩ := Nat.exists_eq_add_of_le hn have := hmono d omega
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Finset.card_eq_one.mp- A finite set has cardinality 1 if and only if it is a singleton set.
Finset.exists_min_image- A nonempty finite set has an element that minimizes any given function into a linearly ordered type.
Finset.le_sup- The value of a function at any element of a finite set is bounded above by the supremum of the function over that set.
Finset.mem_univ- Every element of a finite type belongs to its universal finset Finset.univ.
Finset.sup_singleton- The supremum of a function over a singleton set is the value of the function at that single element.
Finset.univ- The finite set containing all elements of a finite type.
Nat.exists_eq_add_of_le- If m ≤ n for natural numbers m and n, then n = m + d for some natural number d.
Nat.sInf_mem- Any nonempty set of natural numbers contains its infimum (minimum element).
Prod.fst- The first projection function of a Cartesian product pair.
SimpleGraph.dist_le- The shortest-path distance between two vertices in a graph is bounded above by the length of any walk connecting them.
SimpleGraph.pathGraph_adj- Two vertices in the path graph P_n are adjacent if and only if their index difference is 1.
SimpleGraph.pathGraph_preconnected- The path graph on n vertices is preconnected, meaning every pair of vertices is connected by a walk.
congrArg- If two arguments are equal, the values of any function applied to them are equal.
le_abs- A number a satisfies a ≤ |b| if and only if a ≤ b or a ≤ -b.
le_rfl- The inequality relation ≤ is reflexive: a ≤ a for all a.
le_trans- The inequality relation ≤ is transitive: if a ≤ b and b ≤ c, then a ≤ c.
multi_label_span- The span of a multi-labeling f, defined as the maximum difference b - a over all vertices x, y and labels a ∈ f(x), b ∈ f(y).
path_graph_dist_le_add- In the path graph P_n, the shortest-path distance between vertex i and vertex i + d is at most d.
path_graph_dist_le_sub- For vertices x ≤ y in the path graph P_n, their shortest-path distance is at most y - x.
path_radio_sep- The condition that two natural numbers x and y satisfy |x - y| ≥ k, expressed as x + k ≤ y ∨ y + k ≤ x.
radio_three_one_path_eight_core- No sequence of eight labels in {0, ..., 6} can satisfy the pairwise separation condition |b_i - b_j| ≥ 4 - |i - j| for all 1 ≤ |i - j| ≤ 3.
radio_three_one_path_eight_span_ge- Every valid (1, 3)-multi-radio labeling of the path graph P_8 has span at least 7.
simple_graph_multi_radio_number- The multi-radio number of a graph, defined as the infimum of the spans of all its valid (m, k)-multi-radio labelings.
simple_graph_multi_radio_number_path_le_eight_mul- The (m, 3)-multi-radio number of the path graph P_n is at most 8m - 1.
simple_graph_multi_radio_number_path_mono- The (m, k)-multi-radio number of path graphs is non-decreasing with respect to the number of vertices.
simple_graph_multi_radio_number_path_mono_exists_labeling- Every finite simple graph admits at least one valid (m, k)-multi-radio labeling.
- The core lemma radio_three_one_path_eight_core (Step 1) is proved by decide +kernel, which performs an exhaustive computational verification showing no assignment of 8 labels in Fin 7 satisfies the pairwise separation conditions.
- To relate shortest-path distance on the path graph P_n to index subtraction, the proof explicitly proves path_graph_dist_le_add by induction using walk lengths and the triangle inequality on connected graphs.
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.
/-- Separation `|x - y| ≥ k` of two labels, in ℕ. -/def path_radio_sep (k x y : ℕ) : Prop := x + k ≤ y ∨ y + k ≤ xset_option synthInstance.maxSize 100000 inset_option synthInstance.maxHeartbeats 1000000 inset_option maxHeartbeats 4000000 intheorem radio_three_one_path_eight_core : ∀ b0 : Fin 7, ∀ b1 : Fin 7, path_radio_sep 3 b0.val b1.val → ∀ b2 : Fin 7, path_radio_sep 2 b0.val b2.val → path_radio_sep 3 b1.val b2.val → ∀ b3 : Fin 7, path_radio_sep 1 b0.val b3.val → path_radio_sep 2 b1.val b3.val → path_radio_sep 3 b2.val b3.val → ∀ b4 : Fin 7, path_radio_sep 1 b1.val b4.val → path_radio_sep 2 b2.val b4.val → path_radio_sep 3 b3.val b4.val → ∀ b5 : Fin 7, path_radio_sep 1 b2.val b5.val → path_radio_sep 2 b3.val b5.val → path_radio_sep 3 b4.val b5.val → ∀ b6 : Fin 7, path_radio_sep 1 b3.val b6.val → path_radio_sep 2 b4.val b6.val → path_radio_sep 3 b5.val b6.val → ∀ b7 : Fin 7, path_radio_sep 1 b4.val b7.val → path_radio_sep 2 b5.val b7.val → path_radio_sep 3 b6.val b7.val → False := by unfold path_radio_sep decide +kerneltheorem path_graph_dist_le_add (n i d : ℕ) (h : i + d < n) : (SimpleGraph.pathGraph n).dist ⟨i, by omega⟩ ⟨i + d, h⟩ ≤ d := by induction d with | zero => simp | succ d ih => have : Nonempty (Fin n) := ⟨⟨i, by omega⟩⟩ have hc : (SimpleGraph.pathGraph n).Connected := ⟨SimpleGraph.pathGraph_preconnected n⟩ have hadj : (SimpleGraph.pathGraph n).Adj ⟨i + d, by omega⟩ ⟨i + (d + 1), h⟩ := by rw [SimpleGraph.pathGraph_adj]; left; simp; omega have h1 : (SimpleGraph.pathGraph n).dist ⟨i + d, by omega⟩ ⟨i + (d + 1), h⟩ ≤ 1 := by have := SimpleGraph.dist_le hadj.toWalk; simpa using this have h2 := ih (by omega) have h3 := hc.dist_triangle (u := ⟨i, by omega⟩) (v := ⟨i + d, by omega⟩) (w := ⟨i + (d + 1), h⟩) omegatheorem path_graph_dist_le_sub {n : ℕ} (x y : Fin n) (hxy : x.val ≤ y.val) : (SimpleGraph.pathGraph n).dist x y ≤ y.val - x.val := by have := path_graph_dist_le_add n x.val (y.val - x.val) (by omega) have hy : (⟨x.val + (y.val - x.val), by omega⟩ : Fin n) = y := Fin.ext (by simp; omega) rw [hy] at this simpa using thistheorem radio_three_one_path_eight_span_ge (f : Fin 8 → Finset ℕ) (hf : simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph 8) 1 3 f) : 7 ≤ multi_label_span f := by have h1 : ∀ v, ∃ x, f v = {x} := fun v => Finset.card_eq_one.mp (hf.1 v) choose a ha using h1 have hfa : f = fun v => {a v} := funext ha have hsepZ : ∀ x y : Fin 8, x.val < y.val → (3 + 1 : ℤ) - ((y.val - x.val : ℕ) : ℤ) ≤ |(a x : ℤ) - a y| := by intro x y hxy have hne : (x, a x) ≠ (y, a y) := by intro h; have := congrArg Prod.fst h; simp at this; subst this; omega have := hf.2 x y (a x) (by rw [ha x]; simp) (a y) (by rw [ha y]; simp) hne have hd := path_graph_dist_le_sub x y hxy.le push_cast at this ⊢ have : ((SimpleGraph.pathGraph 8).dist x y : ℤ) ≤ ((y.val - x.val : ℕ) : ℤ) := by exact_mod_cast hd linarith by_contra hlt push Not at hlt have hspan : ∀ x y : Fin 8, a y - a x ≤ 6 := by intro x y have : a y - a x ≤ multi_label_span f := by rw [hfa]; unfold multi_label_span simp only [Finset.sup_singleton] exact le_trans (Finset.le_sup (f := fun y => a y - a x) (Finset.mem_univ y)) (Finset.le_sup (f := fun x => Finset.univ.sup fun y => a y - a x) (Finset.mem_univ x)) omega obtain ⟨i0, -, hi0⟩ := Finset.exists_min_image Finset.univ a ⟨0, Finset.mem_univ _⟩ set b : Fin 8 → ℕ := fun v => a v - a i0 with hbdef have hb : ∀ v, b v < 7 := fun v => by have := hspan i0 v; simp only [hbdef]; omega have hsep : ∀ i j : Fin 8, i.val < j.val → j.val ≤ i.val + 3 → path_radio_sep (4 - (j.val - i.val)) (b i) (b j) := by intro i j hij hj have h := hsepZ i j hij have hi := hi0 i (Finset.mem_univ _) have hj' := hi0 j (Finset.mem_univ _) unfold path_radio_sep; simp only [hbdef] rw [le_abs] at h omega exact radio_three_one_path_eight_core ⟨b 0, hb 0⟩ ⟨b 1, hb 1⟩ (hsep 0 1 (by decide) (by decide)) ⟨b 2, hb 2⟩ (hsep 0 2 (by decide) (by decide)) (hsep 1 2 (by decide) (by decide)) ⟨b 3, hb 3⟩ (hsep 0 3 (by decide) (by decide)) (hsep 1 3 (by decide) (by decide)) (hsep 2 3 (by decide) (by decide)) ⟨b 4, hb 4⟩ (hsep 1 4 (by decide) (by decide)) (hsep 2 4 (by decide) (by decide)) (hsep 3 4 (by decide) (by decide)) ⟨b 5, hb 5⟩ (hsep 2 5 (by decide) (by decide)) (hsep 3 5 (by decide) (by decide)) (hsep 4 5 (by decide) (by decide)) ⟨b 6, hb 6⟩ (hsep 3 6 (by decide) (by decide)) (hsep 4 6 (by decide) (by decide)) (hsep 5 6 (by decide) (by decide)) ⟨b 7, hb 7⟩ (hsep 4 7 (by decide) (by decide)) (hsep 5 7 (by decide) (by decide)) (hsep 6 7 (by decide) (by decide))theorem simple_graph_multi_radio_number_path_three_one_of_le (n : ℕ) (hn : 8 ≤ n) : simple_graph_multi_radio_number (SimpleGraph.pathGraph n) 1 3 = 7 := by have hup := simple_graph_multi_radio_number_path_le_eight_mul n 1 (by omega) le_rfl have h8 : 7 ≤ simple_graph_multi_radio_number (SimpleGraph.pathGraph 8) 1 3 := by have hne : {s | ∃ f, simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph 8) 1 3 f ∧ multi_label_span f = s}.Nonempty := by obtain ⟨f, hf⟩ := simple_graph_multi_radio_number_path_mono_exists_labeling (SimpleGraph.pathGraph 8) 1 3 exact ⟨_, f, hf, rfl⟩ obtain ⟨f, hf, hs⟩ := Nat.sInf_mem hne unfold simple_graph_multi_radio_number rw [← hs] exact radio_three_one_path_eight_span_ge f hf have hmono : ∀ d, simple_graph_multi_radio_number (SimpleGraph.pathGraph 8) 1 3 ≤ simple_graph_multi_radio_number (SimpleGraph.pathGraph (8 + d)) 1 3 := by intro d induction d with | zero => exact le_rfl | succ d ih => exact le_trans ih (simple_graph_multi_radio_number_path_mono (8 + d) 1 3 (by omega)) obtain ⟨d, rfl⟩ := Nat.exists_eq_add_of_le hn have := hmono d omega