AFTD Auto-Formalizing Theoretical Domains

simple_graph_path_radio_three_seven_extremal_unique

theoremverified

The case m = 1: the only (1,3)-radio labelings of P_7 with labels in [0, 6] are 4,1,6,3,0,5,2 and its mirror image.

Statement

theorem simple_graph_path_radio_three_seven_extremal_unique (f : Fin 7 → Finset ℕ)
    (hf : simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph 7) 1 3 f)
    (hb : ∀ v, ∀ a ∈ f v, a ≤ 6) :
    f = ![{4}, {1}, {6}, {3}, {0}, {5}, {2}] ∨ f = ![{2}, {5}, {0}, {3}, {6}, {1}, {4}]
Source
Base case m = 1 of simple_graph_path_radio_three_four_mul_add_three_extremal_unique.
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

The proof classifies all (1, 3)-radio labelings of the path graph P_7 with labels in {0, …, 6}. Since m = 1, each vertex receives a singleton label {x_v}, and the radio condition requires |x_u - x_v| ≥ 4 - dist(u, v) for distinct vertices. Because graph distance in P_7 is bounded by index difference |u - v|, this induces concrete separation constraints: adjacent labels differ by at least 3, distance-2 labels differ by at least 2, and distance-3 labels are distinct. A 64-branch search over the signs of consecutive label differences (discharged by Presburger arithmetic automation) eliminates all but two symmetric solutions: (4, 1, 6, 3, 0, 5, 2) and its mirror image (2, 5, 0, 3, 6, 1, 4).

  1. In the path graph P_n, any vertex i is adjacent to i + 1.

    Unfolding the definition of adjacency in P_n via SimpleGraph.pathGraph_adj, two vertices are adjacent if and only if their index values differ by 1. Because (i + 1) = i + 1, the first alternative holds by reflexivity.

    lines 5–6

    uses SimpleGraph.pathGraph_adj, Or.inl

      rw [SimpleGraph.pathGraph_adj]
      exact Or.inl rfl
  2. If j and w are adjacent in P_n, then dist(i, w) ≤ dist(i, j) + 1 for any vertex i.

    By SimpleGraph.Adj.diff_dist_adj, adjacency guarantees that dist(i, w) is either dist(i, j), dist(i, j) + 1, or dist(i, j) - 1. In all three cases, linear integer arithmetic (omega) confirms that dist(i, w) ≤ dist(i, j) + 1.

    lines 11–15

    uses SimpleGraph.Adj.diff_dist_adj

      have key : (SimpleGraph.pathGraph n).dist i w = (SimpleGraph.pathGraph n).dist i j ∨
          (SimpleGraph.pathGraph n).dist i w = (SimpleGraph.pathGraph n).dist i j + 1 ∨
          (SimpleGraph.pathGraph n).dist i w = (SimpleGraph.pathGraph n).dist i j - 1 :=
        SimpleGraph.Adj.diff_dist_adj h
      omega
  3. In P_n, dist(i, i + k) ≤ k for every k such that i + k < n.

    We induct on k. In the base case k = 0, i + 0 = i and dist(i, i) = 0 by SimpleGraph.dist_self. In the inductive step, vertex i + k is adjacent to i + (k + 1) by simple_graph_path_radio_three_seven_extremal_unique_adj_fin, so simple_graph_path_radio_three_seven_extremal_unique_dist_le_succ implies dist(i, i + k + 1) ≤ dist(i, i + k) + 1 ≤ k + 1.

    lines 19–33

    uses SimpleGraph.dist_self, simple_graph_path_radio_three_seven_extremal_unique_adj_fin, simple_graph_path_radio_three_seven_extremal_unique_dist_le_succ

      intro k
      induction k with
      | zero =>
        intro h
        have hh : (⟨i.val + 0, h⟩ : Fin n) = i := by ext; simp
        rw [hh, SimpleGraph.dist_self]
      | succ k ih =>
        intro h
        have h' : i.val + k < n := by omega
        have hadj : (SimpleGraph.pathGraph n).Adj ⟨i.val + k, h'⟩ ⟨i.val + (k + 1), h⟩ :=
          simple_graph_path_radio_three_seven_extremal_unique_adj_fin ⟨i.val + k, h'⟩
            (by show i.val + k + 1 < n; omega)
        have hstep := simple_graph_path_radio_three_seven_extremal_unique_dist_le_succ (i := i) hadj
        have hih := ih h'
        omega
  4. In P_n, the graph distance dist(u, v) is at most |u - v|.

    By totality of the order (le_total), either u ≤ v or v ≤ u. If u ≤ v, v = u + (v - u), and simple_graph_path_radio_three_seven_extremal_unique_dist_le_add bounds dist(u, v) by v - u = |u - v|. Symmetrically, if v ≤ u, the same lemma combined with symmetry of distance (SimpleGraph.dist_comm) gives dist(u, v) = dist(v, u) ≤ u - v = |u - v|.

    lines 37–64

    uses le_total, simple_graph_path_radio_three_seven_extremal_unique_dist_le_add, Fin.ext, abs_of_nonpos, SimpleGraph.dist_comm, abs_of_nonneg

      rcases le_total u.val v.val with h | h
      · have h1 : (SimpleGraph.pathGraph n).dist u v ≤ v.val - u.val := by
          have hbound := simple_graph_path_radio_three_seven_extremal_unique_dist_le_add u
            (v.val - u.val) (by omega)
          have hv : (⟨u.val + (v.val - u.val), (by omega)⟩ : Fin n) = v := by
            apply Fin.ext
            show u.val + (v.val - u.val) = v.val
            omega
          rwa [hv] at hbound
        have h3 : |((u : ℕ) : ℤ) - ((v : ℕ) : ℤ)| = ((v.val - u.val : ℕ) : ℤ) := by
          rw [abs_of_nonpos] <;> omega
        calc (((SimpleGraph.pathGraph n).dist u v : ℕ) : ℤ) ≤ ((v.val - u.val : ℕ) : ℤ) := by
              exact_mod_cast h1
          _ = |((u : ℕ) : ℤ) - ((v : ℕ) : ℤ)| := h3.symm
      · have h1 : (SimpleGraph.pathGraph n).dist u v ≤ u.val - v.val := by
          have hbound := simple_graph_path_radio_three_seven_extremal_unique_dist_le_add v
            (u.val - v.val) (by omega)
          have hv : (⟨v.val + (u.val - v.val), (by omega)⟩ : Fin n) = u := by
            apply Fin.ext
            show v.val + (u.val - v.val) = u.val
            omega
          rw [hv, SimpleGraph.dist_comm] at hbound
          exact hbound
        have h3 : |((u : ℕ) : ℤ) - ((v : ℕ) : ℤ)| = ((u.val - v.val : ℕ) : ℤ) := by
          rw [abs_of_nonneg] <;> omega
        calc (((SimpleGraph.pathGraph n).dist u v : ℕ) : ℤ) ≤ ((u.val - v.val : ℕ) : ℤ) := by
              exact_mod_cast h1
          _ = |((u : ℕ) : ℤ) - ((v : ℕ) : ℤ)| := h3.symm
  5. If c ≤ |p - q| for natural numbers p, q, c, then p + c ≤ q or q + c ≤ p.

    Expanding the absolute value inequality via le_abs.mp yields c ≤ p - q or c ≤ -(p - q). Linear integer arithmetic (omega) translates these into p + c ≤ q or q + c ≤ p.

    line 68

    uses le_abs.mp

      rcases le_abs.mp h with h' | h' <;> omega
  6. If 1 ≤ |p - q| for natural numbers p and q, then p ≠ q.

    Specialising simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ge to c = 1 gives p + 1 ≤ q or q + 1 ≤ p, both of which rule out p = q.

    lines 72–73

    uses simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ge

      rcases simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ge (c := 1) h with
        h' | h' <;> omega
  7. If D ≤ 4, dist(u, v) ≤ D, and 4 - dist(u, v) ≤ |p - q|, then p + (4 - D) ≤ q or q + (4 - D) ≤ p.

    Since dist(u, v) ≤ D, we have 4 - D ≤ 4 - dist(u, v) ≤ |p - q|. Applying simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ge with constant c = 4 - D establishes the disjunction.

    lines 80–84

    uses Nat.cast_sub, simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ge

      have hcast : ((4 - D : ℕ) : ℤ) = 4 - (D : ℤ) := by
        rw [Nat.cast_sub hD4]; norm_num
      apply simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ge
      rw [hcast]
      omega
  8. If D ≤ 3, dist(u, v) ≤ D, and 4 - dist(u, v) ≤ |p - q|, then p ≠ q.

    From D ≤ 3 and dist(u, v) ≤ D, we have 1 ≤ 4 - D ≤ 4 - dist(u, v) ≤ |p - q|. By simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ne, this forces p ≠ q.

    line 91

    uses simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ne

      simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ne (by omega)
  9. Any tuple (x₀, …, x₆) with values in [0, 6] satisfying the 15 radio separation constraints must be either (4, 1, 6, 3, 0, 5, 2) or (2, 5, 0, 3, 6, 1, 4). automation

    We perform a case split on the signs of the six consecutive differences |x_{i+1} - x_i| ≥ 3, generating 2⁶ = 64 branches. For each branch, Presburger arithmetic automation (omega) combines the sign choices with the upper bounds x_i ≤ 6, the distance-2 inequalities |x_{i+2} - x_i| ≥ 2, and the distance-3 inequalities x_{i+3} ≠ x_i. In 62 branches omega derives a contradiction, while in the remaining two branches it uniquely solves for the two stated assignments.

    lines 106–113

    uses Or.inl, Or.inr

      rcases h01 with h01 | h01 <;> rcases h12 with h12 | h12 <;>
        rcases h23 with h23 | h23 <;> rcases h34 with h34 | h34 <;>
        rcases h45 with h45 | h45 <;> rcases h56 with h56 | h56
      all_goals
        first
          | (exfalso; omega)
          | exact Or.inl (by omega)
          | exact Or.inr (by omega)
  10. Each set f(v) is a singleton {x(v)} whose unique element satisfies x(v) ≤ 6.

    Because f is a (1, 3)-radio labeling, |f(v)| = 1 for each vertex v. By Finset.card_eq_one.mp, there exists a choice function x with f(v) = {x(v)}. The hypothesis hb bounds every element in f(v) by 6, which directly gives x(v) ≤ 6.

    lines 119–125

    uses Finset.card_eq_one.mp, Finset.mem_singleton_self

      obtain ⟨hcard, hradio⟩ := hf
      obtain ⟨x, hx⟩ : ∃ x : Fin 7 → ℕ, ∀ v, f v = {x v} := by
        choose y hy using fun v => Finset.card_eq_one.mp (hcard v)
        exact ⟨y, hy⟩
      have hx6 : ∀ v, x v ≤ 6 := by
        intro v
        exact hb v (x v) (by rw [hx v]; exact Finset.mem_singleton_self (x v))
  11. For any distinct vertices i ≠ j, 4 - dist(i, j) ≤ |x(i) - x(j)|, and if |i - j| = D then dist(i, j) ≤ D.

    Since i ≠ j, the pairs (i, x(i)) and (j, x(j)) are distinct, so the definition of a (1, 3)-radio labeling gives (3 + 1) - dist(i, j) ≤ |x(i) - x(j)|. Furthermore, simple_graph_path_radio_three_seven_extremal_unique_dist_le_abs shows that the graph distance dist(i, j) is at most |i - j| = D.

    lines 126–137

    uses congrArg, Prod.fst, Finset.mem_singleton_self, simple_graph_path_radio_three_seven_extremal_unique_dist_le_abs

      have hcon : ∀ i j : Fin 7, i ≠ j →
          (4 : ℤ) - (((SimpleGraph.pathGraph 7).dist i j : ℕ) : ℤ) ≤ |(x i : ℤ) - (x j : ℤ)| := by
        intro i j hij
        have hne : (i, x i) ≠ (j, x j) := fun h => hij (congrArg Prod.fst h)
        have h := hradio i j (x i) (by rw [hx i]; exact Finset.mem_singleton_self _)
          (x j) (by rw [hx j]; exact Finset.mem_singleton_self _) hne
        simpa using h
      have d : ∀ (i j : Fin 7) (D : ℕ), |((i : ℕ) : ℤ) - ((j : ℕ) : ℤ)| = (D : ℤ) →
          (((SimpleGraph.pathGraph 7).dist i j : ℕ) : ℤ) ≤ (D : ℤ) := by
        intro i j D hD
        have h := simple_graph_path_radio_three_seven_extremal_unique_dist_le_abs (n := 7) i j
        omega
  12. The values x(0), …, x(6) satisfy the 15 separation conditions required by the core classification lemma.

    For consecutive vertices (|i - j| = 1), dist(i, j) ≤ 1, so simple_graph_path_radio_three_seven_extremal_unique_disj with D = 1 yields |x(i) - x(j)| ≥ 4 - 1 = 3 (6 conditions). For vertices at index difference 2, dist(i, j) ≤ 2, so the same lemma with D = 2 yields |x(i) - x(j)| ≥ 2 (5 conditions). For vertices at index difference 3, dist(i, j) ≤ 3, so simple_graph_path_radio_three_seven_extremal_unique_ne with D = 3 yields x(i) ≠ x(j) (4 conditions).

    lines 138–182

    uses simple_graph_path_radio_three_seven_extremal_unique_disj, simple_graph_path_radio_three_seven_extremal_unique_ne

      have h01 : x 0 + 3 ≤ x 1 ∨ x 1 + 3 ≤ x 0 :=
        simple_graph_path_radio_three_seven_extremal_unique_disj (D := 1) (by norm_num)
          (d 0 1 1 (by norm_num)) (hcon 0 1 (by decide))
      have h12 : x 1 + 3 ≤ x 2 ∨ x 2 + 3 ≤ x 1 :=
        simple_graph_path_radio_three_seven_extremal_unique_disj (D := 1) (by norm_num)
          (d 1 2 1 (by norm_num)) (hcon 1 2 (by decide))
      have h23 : x 2 + 3 ≤ x 3 ∨ x 3 + 3 ≤ x 2 :=
        simple_graph_path_radio_three_seven_extremal_unique_disj (D := 1) (by norm_num)
          (d 2 3 1 (by norm_num)) (hcon 2 3 (by decide))
      have h34 : x 3 + 3 ≤ x 4 ∨ x 4 + 3 ≤ x 3 :=
        simple_graph_path_radio_three_seven_extremal_unique_disj (D := 1) (by norm_num)
          (d 3 4 1 (by norm_num)) (hcon 3 4 (by decide))
      have h45 : x 4 + 3 ≤ x 5 ∨ x 5 + 3 ≤ x 4 :=
        simple_graph_path_radio_three_seven_extremal_unique_disj (D := 1) (by norm_num)
          (d 4 5 1 (by norm_num)) (hcon 4 5 (by decide))
      have h56 : x 5 + 3 ≤ x 6 ∨ x 6 + 3 ≤ x 5 :=
        simple_graph_path_radio_three_seven_extremal_unique_disj (D := 1) (by norm_num)
          (d 5 6 1 (by norm_num)) (hcon 5 6 (by decide))
      have h02 : x 0 + 2 ≤ x 2 ∨ x 2 + 2 ≤ x 0 :=
        simple_graph_path_radio_three_seven_extremal_unique_disj (D := 2) (by norm_num)
          (d 0 2 2 (by norm_num)) (hcon 0 2 (by decide))
      have h13 : x 1 + 2 ≤ x 3 ∨ x 3 + 2 ≤ x 1 :=
        simple_graph_path_radio_three_seven_extremal_unique_disj (D := 2) (by norm_num)
          (d 1 3 2 (by norm_num)) (hcon 1 3 (by decide))
      have h24 : x 2 + 2 ≤ x 4 ∨ x 4 + 2 ≤ x 2 :=
        simple_graph_path_radio_three_seven_extremal_unique_disj (D := 2) (by norm_num)
          (d 2 4 2 (by norm_num)) (hcon 2 4 (by decide))
      have h35 : x 3 + 2 ≤ x 5 ∨ x 5 + 2 ≤ x 3 :=
        simple_graph_path_radio_three_seven_extremal_unique_disj (D := 2) (by norm_num)
          (d 3 5 2 (by norm_num)) (hcon 3 5 (by decide))
      have h46 : x 4 + 2 ≤ x 6 ∨ x 6 + 2 ≤ x 4 :=
        simple_graph_path_radio_three_seven_extremal_unique_disj (D := 2) (by norm_num)
          (d 4 6 2 (by norm_num)) (hcon 4 6 (by decide))
      have h03 : x 0 ≠ x 3 :=
        simple_graph_path_radio_three_seven_extremal_unique_ne (D := 3) (by norm_num)
          (d 0 3 3 (by norm_num)) (hcon 0 3 (by decide))
      have h14 : x 1 ≠ x 4 :=
        simple_graph_path_radio_three_seven_extremal_unique_ne (D := 3) (by norm_num)
          (d 1 4 3 (by norm_num)) (hcon 1 4 (by decide))
      have h25 : x 2 ≠ x 5 :=
        simple_graph_path_radio_three_seven_extremal_unique_ne (D := 3) (by norm_num)
          (d 2 5 3 (by norm_num)) (hcon 2 5 (by decide))
      have h36 : x 3 ≠ x 6 :=
        simple_graph_path_radio_three_seven_extremal_unique_ne (D := 3) (by norm_num)
          (d 3 6 3 (by norm_num)) (hcon 3 6 (by decide))
  13. f = ![{4}, {1}, {6}, {3}, {0}, {5}, {2}] ∨ f = ![{2}, {5}, {0}, {3}, {6}, {1}, {4}].

    Applying simple_graph_path_radio_three_seven_extremal_unique_core to the values x(0), …, x(6) shows that the sequence of labels must be either 4, 1, 6, 3, 0, 5, 2 or 2, 5, 0, 3, 6, 1, 4. In each case, substituting f(v) = {x(v)} and checking each vertex v ∈ Fin 7 via fin_cases establishes functional equality with the explicit singleton-valued array.

    lines 183–194

    uses simple_graph_path_radio_three_seven_extremal_unique_core

      rcases simple_graph_path_radio_three_seven_extremal_unique_core (x 0) (x 1) (x 2) (x 3) (x 4)
        (x 5) (x 6) (hx6 0) (hx6 1) (hx6 2) (hx6 3) (hx6 4) (hx6 5) (hx6 6)
        h01 h12 h23 h34 h45 h56 h02 h13 h24 h35 h46 h03 h14 h25 h36 with
        ⟨e0, e1, e2, e3, e4, e5, e6⟩ | ⟨e0, e1, e2, e3, e4, e5, e6⟩
      · left
        funext v
        rw [hx v]
        fin_cases v <;> simp [e0, e1, e2, e3, e4, e5, e6]
      · right
        funext v
        rw [hx v]
        fin_cases v <;> simp [e0, e1, e2, e3, e4, e5, e6]
SimpleGraph.pathGraph_adj
In a path graph P_n, two vertices u and v are adjacent if and only if their index values differ by 1.
Or.inl
If proposition A holds, then the disjunction A ∨ B holds.
SimpleGraph.Adj.diff_dist_adj
If v and w are adjacent in a graph G, the distance from any vertex u to w differs from the distance from u to v by at most 1 (it is either dist u v, dist u v + 1, or dist u v - 1).
SimpleGraph.dist_self
The distance from any vertex in a graph to itself is 0.
simple_graph_path_radio_three_seven_extremal_unique_adj_fin
In P_n, vertex i is adjacent to i + 1 whenever i + 1 < n.
simple_graph_path_radio_three_seven_extremal_unique_dist_le_succ
If j and w are adjacent in P_n, the distance from any vertex i to w is at most the distance from i to j plus 1.
le_total
In a linearly ordered type, for any elements a and b, either a ≤ b or b ≤ a.
simple_graph_path_radio_three_seven_extremal_unique_dist_le_add
In P_n, the distance between vertex i and vertex i + k is at most k.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural values are equal.
abs_of_nonpos
If a ≤ 0, then the absolute value |a| equals -a.
SimpleGraph.dist_comm
Graph distance is symmetric: the distance from u to v equals the distance from v to u.
abs_of_nonneg
If 0 ≤ a, then the absolute value |a| equals a.
le_abs.mp
If c ≤ |a|, then either c ≤ a or c ≤ -a.
simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ge
For natural numbers p, q, c, if c ≤ |p - q|, then either p + c ≤ q or q + c ≤ p.
Nat.cast_sub
For natural numbers with m ≤ n, the integer cast of n - m equals the difference of the integer casts n - m.
simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ne
If 1 ≤ |p - q| for natural numbers p and q, then p ≠ q.
Or.inr
If proposition B holds, then the disjunction A ∨ B holds.
Finset.card_eq_one.mp
A finite set has cardinality 1 if and only if it is of the form {a} for some element a.
Finset.mem_singleton_self
Any element a belongs to the singleton set {a}.
congrArg
Equality is preserved under applying a function: if x = y, then g x = g y.
Prod.fst
The first projection of an ordered pair (a, b) is a.
simple_graph_path_radio_three_seven_extremal_unique_dist_le_abs
In the path graph P_n, the graph distance between vertices u and v is bounded above by |u - v|.
simple_graph_path_radio_three_seven_extremal_unique_disj
If D ≤ 4, dist(u, v) ≤ D, and 4 - dist(u, v) ≤ |p - q|, then either p + (4 - D) ≤ q or q + (4 - D) ≤ p.
simple_graph_path_radio_three_seven_extremal_unique_ne
If D ≤ 3, dist(u, v) ≤ D, and 4 - dist(u, v) ≤ |p - q|, then p ≠ q.
simple_graph_path_radio_three_seven_extremal_unique_core
The only labelings of seven vertices with labels in [0, 6] satisfying the radio distance constraints on P_7 are (4, 1, 6, 3, 0, 5, 2) and (2, 5, 0, 3, 6, 1, 4).

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

Lean’s trace was cut to the first 400 of 434 tactics.

set_option maxHeartbeats 1000000 inlemma simple_graph_path_radio_three_seven_extremal_unique_adj_fin {n : ℕ} (i : Fin n)    (h : i.val + 1 < n) :    (SimpleGraph.pathGraph n).Adj i ⟨i.val + 1, h⟩ := by  rw [SimpleGraph.pathGraph_adj]  exact Or.inl rfllemma simple_graph_path_radio_three_seven_extremal_unique_dist_le_succ {n : ℕ} {i j w : Fin n}    (h : (SimpleGraph.pathGraph n).Adj j w) :    (SimpleGraph.pathGraph n).dist i w ≤ (SimpleGraph.pathGraph n).dist i j + 1 := by  have key : (SimpleGraph.pathGraph n).dist i w = (SimpleGraph.pathGraph n).dist i j ∨      (SimpleGraph.pathGraph n).dist i w = (SimpleGraph.pathGraph n).dist i j + 1 ∨      (SimpleGraph.pathGraph n).dist i w = (SimpleGraph.pathGraph n).dist i j - 1 :=    SimpleGraph.Adj.diff_dist_adj h  omegalemma simple_graph_path_radio_three_seven_extremal_unique_dist_le_add {n : ℕ} (i : Fin n) :    ∀ (k : ℕ) (h : i.val + k < n), (SimpleGraph.pathGraph n).dist i ⟨i.val + k, h⟩ ≤ k := by  intro k  induction k with  | zero =>    intro h    have hh : (⟨i.val + 0, h⟩ : Fin n) = i := by ext; simp    rw [hh, SimpleGraph.dist_self]  | succ k ih =>    intro h    have h' : i.val + k < n := by omega    have hadj : (SimpleGraph.pathGraph n).Adj ⟨i.val + k, h'⟩ ⟨i.val + (k + 1), h⟩ :=      simple_graph_path_radio_three_seven_extremal_unique_adj_fin ⟨i.val + k, h'⟩        (by show i.val + k + 1 < n; omega)    have hstep := simple_graph_path_radio_three_seven_extremal_unique_dist_le_succ (i := i) hadj    have hih := ih h'    omegalemma simple_graph_path_radio_three_seven_extremal_unique_dist_le_abs {n : ℕ} (u v : Fin n) :    (((SimpleGraph.pathGraph n).dist u v : ℕ) : ℤ) ≤ |((u : ℕ) : ℤ) - ((v : ℕ) : ℤ)| := by  rcases le_total u.val v.val with h | h  · have h1 : (SimpleGraph.pathGraph n).dist u v ≤ v.val - u.val := by      have hbound := simple_graph_path_radio_three_seven_extremal_unique_dist_le_add u        (v.val - u.val) (by omega)      have hv : (⟨u.val + (v.val - u.val), (by omega)⟩ : Fin n) = v := by        apply Fin.ext        show u.val + (v.val - u.val) = v.val        omega      rwa [hv] at hbound    have h3 : |((u : ℕ) : ℤ) - ((v : ℕ) : ℤ)| = ((v.val - u.val : ℕ) : ℤ) := by      rw [abs_of_nonpos] <;> omega    calc (((SimpleGraph.pathGraph n).dist u v : ℕ) : ℤ) ≤ ((v.val - u.val : ℕ) : ℤ) := by          exact_mod_cast h1      _ = |((u : ℕ) : ℤ) - ((v : ℕ) : ℤ)| := h3.symm  · have h1 : (SimpleGraph.pathGraph n).dist u v ≤ u.val - v.val := by      have hbound := simple_graph_path_radio_three_seven_extremal_unique_dist_le_add v        (u.val - v.val) (by omega)      have hv : (⟨v.val + (u.val - v.val), (by omega)⟩ : Fin n) = u := by        apply Fin.ext        show v.val + (u.val - v.val) = u.val        omega      rw [hv, SimpleGraph.dist_comm] at hbound      exact hbound    have h3 : |((u : ℕ) : ℤ) - ((v : ℕ) : ℤ)| = ((u.val - v.val : ℕ) : ℤ) := by      rw [abs_of_nonneg] <;> omega    calc (((SimpleGraph.pathGraph n).dist u v : ℕ) : ℤ) ≤ ((u.val - v.val : ℕ) : ℤ) := by          exact_mod_cast h1      _ = |((u : ℕ) : ℤ) - ((v : ℕ) : ℤ)| := h3.symmlemma simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ge {p q c : ℕ}    (h : (c : ℤ) ≤ |(p : ℤ) - (q : ℤ)|) : p + c ≤ q ∨ q + c ≤ p := by  rcases le_abs.mp h with h' | h' <;> omegalemma simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ne {p q : ℕ}    (h : (1 : ℤ) ≤ |(p : ℤ) - (q : ℤ)|) : p ≠ q := by  rcases simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ge (c := 1) h with    h' | h' <;> omegalemma simple_graph_path_radio_three_seven_extremal_unique_disj {n : ℕ} {u v : Fin n}    {p q D : ℕ} (hD4 : D ≤ 4)    (hD : (((SimpleGraph.pathGraph n).dist u v : ℕ) : ℤ) ≤ (D : ℤ))    (hcon : (4 : ℤ) - (((SimpleGraph.pathGraph n).dist u v : ℕ) : ℤ) ≤ |(p : ℤ) - (q : ℤ)|) :    p + (4 - D) ≤ q ∨ q + (4 - D) ≤ p := by  have hcast : ((4 - D : ℕ) : ℤ) = 4 - (D : ℤ) := by    rw [Nat.cast_sub hD4]; norm_num  apply simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ge  rw [hcast]  omegalemma simple_graph_path_radio_three_seven_extremal_unique_ne {n : ℕ} {u v : Fin n}    {p q D : ℕ} (hD3 : D ≤ 3)    (hD : (((SimpleGraph.pathGraph n).dist u v : ℕ) : ℤ) ≤ (D : ℤ))    (hcon : (4 : ℤ) - (((SimpleGraph.pathGraph n).dist u v : ℕ) : ℤ) ≤ |(p : ℤ) - (q : ℤ)|) :    p ≠ q :=  simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ne (by omega)set_option maxHeartbeats 2000000 inlemma simple_graph_path_radio_three_seven_extremal_unique_core (x0 x1 x2 x3 x4 x5 x6 : ℕ)    (b0 : x0 ≤ 6) (b1 : x1 ≤ 6) (b2 : x2 ≤ 6) (b3 : x3 ≤ 6) (b4 : x4 ≤ 6)    (b5 : x5 ≤ 6) (b6 : x6 ≤ 6)    (h01 : x0 + 3 ≤ x1 ∨ x1 + 3 ≤ x0) (h12 : x1 + 3 ≤ x2 ∨ x2 + 3 ≤ x1)    (h23 : x2 + 3 ≤ x3 ∨ x3 + 3 ≤ x2) (h34 : x3 + 3 ≤ x4 ∨ x4 + 3 ≤ x3)    (h45 : x4 + 3 ≤ x5 ∨ x5 + 3 ≤ x4) (h56 : x5 + 3 ≤ x6 ∨ x6 + 3 ≤ x5)    (h02 : x0 + 2 ≤ x2 ∨ x2 + 2 ≤ x0) (h13 : x1 + 2 ≤ x3 ∨ x3 + 2 ≤ x1)    (h24 : x2 + 2 ≤ x4 ∨ x4 + 2 ≤ x2) (h35 : x3 + 2 ≤ x5 ∨ x5 + 2 ≤ x3)    (h46 : x4 + 2 ≤ x6 ∨ x6 + 2 ≤ x4)    (h03 : x0 ≠ x3) (h14 : x1 ≠ x4) (h25 : x2 ≠ x5) (h36 : x3 ≠ x6) :    (x0 = 4 ∧ x1 = 1 ∧ x2 = 6 ∧ x3 = 3 ∧ x4 = 0 ∧ x5 = 5 ∧ x6 = 2) ∨    (x0 = 2 ∧ x1 = 5 ∧ x2 = 0 ∧ x3 = 3 ∧ x4 = 6 ∧ x5 = 1 ∧ x6 = 4) := by  rcases h01 with h01 | h01 <;> rcases h12 with h12 | h12 <;>    rcases h23 with h23 | h23 <;> rcases h34 with h34 | h34 <;>    rcases h45 with h45 | h45 <;> rcases h56 with h56 | h56  all_goals    first      | (exfalso; omega)      | exact Or.inl (by omega)      | exact Or.inr (by omega)theorem simple_graph_path_radio_three_seven_extremal_unique (f : Fin 7 → Finset ℕ)    (hf : simple_graph_is_multi_radio_labeling (SimpleGraph.pathGraph 7) 1 3 f)    (hb : ∀ v, ∀ a ∈ f v, a ≤ 6) :    f = ![{4}, {1}, {6}, {3}, {0}, {5}, {2}] ∨ f = ![{2}, {5}, {0}, {3}, {6}, {1}, {4}] := by  obtain ⟨hcard, hradio⟩ := hf  obtain ⟨x, hx⟩ : ∃ x : Fin 7 → ℕ, ∀ v, f v = {x v} := by    choose y hy using fun v => Finset.card_eq_one.mp (hcard v)    exact ⟨y, hy⟩  have hx6 : ∀ v, x v ≤ 6 := by    intro v    exact hb v (x v) (by rw [hx v]; exact Finset.mem_singleton_self (x v))  have hcon : ∀ i j : Fin 7, i ≠ j →      (4 : ℤ) - (((SimpleGraph.pathGraph 7).dist i j : ℕ) : ℤ) ≤ |(x i : ℤ) - (x j : ℤ)| := by    intro i j hij    have hne : (i, x i) ≠ (j, x j) := fun h => hij (congrArg Prod.fst h)    have h := hradio i j (x i) (by rw [hx i]; exact Finset.mem_singleton_self _)      (x j) (by rw [hx j]; exact Finset.mem_singleton_self _) hne    simpa using h  have d : ∀ (i j : Fin 7) (D : ℕ), |((i : ℕ) : ℤ) - ((j : ℕ) : ℤ)| = (D : ℤ) →      (((SimpleGraph.pathGraph 7).dist i j : ℕ) : ℤ) ≤ (D : ℤ) := by    intro i j D hD    have h := simple_graph_path_radio_three_seven_extremal_unique_dist_le_abs (n := 7) i j    omega  have h01 : x 0 + 3 ≤ x 1 ∨ x 1 + 3 ≤ x 0 :=    simple_graph_path_radio_three_seven_extremal_unique_disj (D := 1) (by norm_num)      (d 0 1 1 (by norm_num)) (hcon 0 1 (by decide))  have h12 : x 1 + 3 ≤ x 2 ∨ x 2 + 3 ≤ x 1 :=    simple_graph_path_radio_three_seven_extremal_unique_disj (D := 1) (by norm_num)      (d 1 2 1 (by norm_num)) (hcon 1 2 (by decide))  have h23 : x 2 + 3 ≤ x 3 ∨ x 3 + 3 ≤ x 2 :=    simple_graph_path_radio_three_seven_extremal_unique_disj (D := 1) (by norm_num)      (d 2 3 1 (by norm_num)) (hcon 2 3 (by decide))  have h34 : x 3 + 3 ≤ x 4 ∨ x 4 + 3 ≤ x 3 :=    simple_graph_path_radio_three_seven_extremal_unique_disj (D := 1) (by norm_num)      (d 3 4 1 (by norm_num)) (hcon 3 4 (by decide))  have h45 : x 4 + 3 ≤ x 5 ∨ x 5 + 3 ≤ x 4 :=    simple_graph_path_radio_three_seven_extremal_unique_disj (D := 1) (by norm_num)      (d 4 5 1 (by norm_num)) (hcon 4 5 (by decide))  have h56 : x 5 + 3 ≤ x 6 ∨ x 6 + 3 ≤ x 5 :=    simple_graph_path_radio_three_seven_extremal_unique_disj (D := 1) (by norm_num)      (d 5 6 1 (by norm_num)) (hcon 5 6 (by decide))  have h02 : x 0 + 2 ≤ x 2 ∨ x 2 + 2 ≤ x 0 :=    simple_graph_path_radio_three_seven_extremal_unique_disj (D := 2) (by norm_num)      (d 0 2 2 (by norm_num)) (hcon 0 2 (by decide))  have h13 : x 1 + 2 ≤ x 3 ∨ x 3 + 2 ≤ x 1 :=    simple_graph_path_radio_three_seven_extremal_unique_disj (D := 2) (by norm_num)      (d 1 3 2 (by norm_num)) (hcon 1 3 (by decide))  have h24 : x 2 + 2 ≤ x 4 ∨ x 4 + 2 ≤ x 2 :=    simple_graph_path_radio_three_seven_extremal_unique_disj (D := 2) (by norm_num)      (d 2 4 2 (by norm_num)) (hcon 2 4 (by decide))  have h35 : x 3 + 2 ≤ x 5 ∨ x 5 + 2 ≤ x 3 :=    simple_graph_path_radio_three_seven_extremal_unique_disj (D := 2) (by norm_num)      (d 3 5 2 (by norm_num)) (hcon 3 5 (by decide))  have h46 : x 4 + 2 ≤ x 6 ∨ x 6 + 2 ≤ x 4 :=    simple_graph_path_radio_three_seven_extremal_unique_disj (D := 2) (by norm_num)      (d 4 6 2 (by norm_num)) (hcon 4 6 (by decide))  have h03 : x 0 ≠ x 3 :=    simple_graph_path_radio_three_seven_extremal_unique_ne (D := 3) (by norm_num)      (d 0 3 3 (by norm_num)) (hcon 0 3 (by decide))  have h14 : x 1 ≠ x 4 :=    simple_graph_path_radio_three_seven_extremal_unique_ne (D := 3) (by norm_num)      (d 1 4 3 (by norm_num)) (hcon 1 4 (by decide))  have h25 : x 2 ≠ x 5 :=    simple_graph_path_radio_three_seven_extremal_unique_ne (D := 3) (by norm_num)      (d 2 5 3 (by norm_num)) (hcon 2 5 (by decide))  have h36 : x 3 ≠ x 6 :=    simple_graph_path_radio_three_seven_extremal_unique_ne (D := 3) (by norm_num)      (d 3 6 3 (by norm_num)) (hcon 3 6 (by decide))  rcases simple_graph_path_radio_three_seven_extremal_unique_core (x 0) (x 1) (x 2) (x 3) (x 4)    (x 5) (x 6) (hx6 0) (hx6 1) (hx6 2) (hx6 3) (hx6 4) (hx6 5) (hx6 6)    h01 h12 h23 h34 h45 h56 h02 h13 h24 h35 h46 h03 h14 h25 h36 with    ⟨e0, e1, e2, e3, e4, e5, e6⟩ | ⟨e0, e1, e2, e3, e4, e5, e6⟩  · left    funext v    rw [hx v]    fin_cases v <;> simp [e0, e1, e2, e3, e4, e5, e6]  · right    funext v    rw [hx v]    fin_cases v <;> simp [e0, e1, e2, e3, e4, e5, e6]
See it in the graphDiscuss this resultChallenge it