AFTD Auto-Formalizing Theoretical Domains

simple_graph_multi_radio_number_path_three_lt

theoremverifiedoriginal

The threshold 4m + 4 is sharp: the (m,3)-radio number of P_{4m+3} is less than 8m - 1.

Statement

theorem simple_graph_multi_radio_number_path_three_lt (m : ℕ) (hm : 1 ≤ m) :
    simple_graph_multi_radio_number (SimpleGraph.pathGraph (4 * m + 3)) m 3 < 8 * m - 1
Related work
arXiv:2610.25863 (On Multi-label radio Labelings of Graphs), Conjecture 1 (case k = 3): the conjecture leaves n0 unspecified
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The proof establishes the upper bound by exhibiting an explicit (m,3)-multi-radio labeling of the path graph P_{4m+3}. A previously proven construction guarantees that this labeling has span at most 8m - 2. Since the multi-radio number is defined as the infimum of all achievable spans, it is at most 8m - 2, which is strictly less than 8m - 1.

  1. There exists a valid (m,3)-multi-radio labeling of P_{4m+3} with span at most 8m - 2.

    Applying the lemma simple_graph_path_radio_labeling_four_mul_add_three produces an explicit labeling f on the path graph P_{4m+3}, together with proofs that f is a valid (m,3)-multi-radio labeling (hf) and that its span satisfies multi_label_span f ≤ 8m - 2 (hs).

    line 3

    uses simple_graph_path_radio_labeling_four_mul_add_three

      obtain ⟨hf, hs⟩ := simple_graph_path_radio_labeling_four_mul_add_three m hm
  2. The infimum of spans of all valid (m,3)-multi-radio labelings of P_{4m+3} is at most the span of this explicit labeling f.

    Since f is an (m,3)-multi-radio labeling, its span belongs to the set of spans of all valid labelings. By Nat.sInf_le, the infimum of this set of natural numbers is bounded above by any element in it, namely multi_label_span f.

    lines 4–6

    uses Nat.sInf_le

      have h := Nat.sInf_le (show multi_label_span _ ∈ {s | ∃ f,
          simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph (4 * m + 3)) m 3 f ∧
            multi_label_span f = s} from ⟨_, hf, rfl⟩)
  3. The (m,3)-multi-radio number of P_{4m+3} is strictly less than 8m - 1.

    Unfolding the definition of simple_graph_multi_radio_number reveals it as the infimum of spans of valid labelings. Linear arithmetic (omega) then combines the bounds sInf ≤ multi_label_span f ≤ 8m - 2 < 8m - 1 to finish the proof.

    lines 7–8

      unfold simple_graph_multi_radio_number
      omega
simple_graph_path_radio_labeling_four_mul_add_three
For any m ≥ 1, there is an explicit (m,3)-multi-radio labeling of the path graph P_{4m+3} whose span is at most 8m - 2.
Nat.sInf_le
If a natural number belongs to a set s ⊆ ℕ, the infimum of s is at most that number.

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_path_three_lt (m : ℕ) (hm : 1 ≤ m) :    simple_graph_multi_radio_number (SimpleGraph.pathGraph (4 * m + 3)) m 3 < 8 * m - 1 := by  obtain ⟨hf, hs⟩ := simple_graph_path_radio_labeling_four_mul_add_three m hm  have h := Nat.sInf_le (show multi_label_span _ ∈ {s | ∃ f,      simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph (4 * m + 3)) m 3 f ∧        multi_label_span f = s} from ⟨_, hf, rfl⟩)  unfold simple_graph_multi_radio_number  omega
See it in the graphDiscuss this resultChallenge it