simple_graph_path_radio_three_seven_extremal_unique
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
- 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…
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).
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.
uses
SimpleGraph.pathGraph_adj,Or.inlrw [SimpleGraph.pathGraph_adj] exact Or.inl rfl
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.
uses
SimpleGraph.Adj.diff_dist_adjhave 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
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.
uses
SimpleGraph.dist_self,simple_graph_path_radio_three_seven_extremal_unique_adj_fin,simple_graph_path_radio_three_seven_extremal_unique_dist_le_succintro 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
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|.
uses
le_total,simple_graph_path_radio_three_seven_extremal_unique_dist_le_add,Fin.ext,abs_of_nonpos,SimpleGraph.dist_comm,abs_of_nonnegrcases 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
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.
uses
le_abs.mprcases le_abs.mp h with h' | h' <;> omega
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.
uses
simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_gercases simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ge (c := 1) h with h' | h' <;> omega
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.
uses
Nat.cast_sub,simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_gehave 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
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.
uses
simple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_nesimple_graph_path_radio_three_seven_extremal_unique_nat_abs_int_ne (by omega)
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.
uses
Or.inl,Or.inrrcases 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)
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.
uses
Finset.card_eq_one.mp,Finset.mem_singleton_selfobtain ⟨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))
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.
uses
congrArg,Prod.fst,Finset.mem_singleton_self,simple_graph_path_radio_three_seven_extremal_unique_dist_le_abshave 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
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).
uses
simple_graph_path_radio_three_seven_extremal_unique_disj,simple_graph_path_radio_three_seven_extremal_unique_nehave 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))
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.
uses
simple_graph_path_radio_three_seven_extremal_unique_corercases 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).
- The classification lemma simple_graph_path_radio_three_seven_extremal_unique_core relies on Lean's Presburger arithmetic solver (omega) over a 64-way branch split to rule out 62 contradictory configurations and uniquely determine the remaining two.
- In Lean, vertices of the path graph P_n are represented by the bounded type Fin n, and distances and labels are cast to integers ℤ to state the radio labeling condition without underflow from natural number subtraction.
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.
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]