tbt_opt_eq_sn_opt_of_is_subcubic
For every finite type V with at least two elements and every subcubic tree T on V, tbt_opt T equals tbt_sn_opt T.
Statement
theorem tbt_opt_eq_sn_opt_of_is_subcubic {V : Type} [Fintype V] (T : SimpleGraph V) (hT : is_subcubic_tree T) (hn : 2 ≤ Fintype.card V) : tbt_opt T = tbt_sn_opt T
- Source
- arXiv:2610.39863, Section 3
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- tbt_optFor a finite type V and a simple graph T on V, tbt_opt T is the infimum in ℕ of the routing costs tree_routing_cost T H id over all…
- tbt_sn_optFor a finite type V and a simple graph T on V, tbt_sn_opt T is the infimum in ℕ of the routing costs tree_routing_cost T H f over all…
- is_subcubic_treeA finite simple graph is a subcubic tree if it is connected, acyclic, and every vertex has degree at most 3.
- tree_routing_costFor any finite type V, type W, simple graph T on V, simple graph H on W, and function f : V → W, tree_routing_cost T H f is the sum over…
Read back from the Lean
Let $V$ be a finite type (in universe Type 0), and let $T$ be a simple graph on $V$. Suppose $T$ is a subcubic tree (that is, $T$ is a tree and every vertex has degree at most 3) and the cardinality of $V$ is at least 2. Then the optimal tree-routing cost without Steiner nodes tbt_opt T is equal to the optimal tree-routing cost with Steiner nodes tbt_sn_opt T.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem states that for any tree T that is already subcubic, the terminal-only routing optimum and the Steiner routing optimum coincide. The proof establishes that both optima equal the number of edges |E(T)|. Since T is subcubic, routing T on itself via the identity map achieves cost |E(T)|, providing an upper bound for both infima; conversely, because any valid host tree is connected, each edge of T must be routed along a path of length at least 1, which bounds any routing cost from below by |E(T)|.
For any edge in T, the distance in H between the images of its endpoints under an embedding f is at least 1.
Unfolding the definition of tree routing cost, each edge e ∈ E(T) can be written as an unordered pair {u, v}. Since u and v are adjacent in T, they are distinct (u ≠ v). Because f is an embedding (hence injective), f(u) ≠ f(v). In any connected graph H, the distance between two distinct vertices is at least 1.
uses
Quot.exists_rep,Sym2.lift_mk,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSetrw [tree_routing_cost] have h_le : ∀ e ∈ T.edgeFinset, 1 ≤ Sym2.lift ⟨fun u v ↦ H.dist (f u) (f v), fun _ _ ↦ H.dist_comm⟩ e := by intro e he obtain ⟨⟨u, v⟩, rfl⟩ := Quot.exists_rep e simp only [Sym2.lift_mk] rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he have hne : u ≠ v := T.ne_of_adj he have hne' : f u ≠ f v := f.injective.ne hne exact hH.pos_dist_of_ne hne'
The routing cost of T in H under an embedding f is at least |E(T)|.
The cardinality |E(T)| equals the sum of 1 over all edges in E(T). Since each edge contributes at least 1 to the routing cost sum, the total sum is at least |E(T)|.
uses
Finset.card_eq_sum_ones,Finset.sum_le_sumhave hcard : T.edgeFinset.card = ∑ e ∈ T.edgeFinset, 1 := Finset.card_eq_sum_ones T.edgeFinset rw [hcard] exact Finset.sum_le_sum h_le
For every edge of T, the distance in T between its endpoints under the identity map is 1.
For any edge e = {u, v} ∈ E(T), the vertices u and v are adjacent in T. In any simple graph, adjacent vertices have distance exactly 1.
uses
Quot.exists_rep,Sym2.lift_mk,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet,SimpleGraph.dist_eq_one_iff_adj.mprrw [tree_routing_cost] have h_eq : ∀ e ∈ T.edgeFinset, Sym2.lift ⟨fun u v ↦ T.dist (id u) (id v), fun _ _ ↦ T.dist_comm⟩ e = 1 := by intro e he obtain ⟨⟨u, v⟩, rfl⟩ := Quot.exists_rep e simp only [Sym2.lift_mk, id] rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he exact SimpleGraph.dist_eq_one_iff_adj.mpr he
The routing cost of T in itself under the identity map equals |E(T)|.
Since every edge summand in the routing cost equals 1, the total cost is the sum of 1 over all edges in E(T), which equals the number of edges |E(T)|.
uses
Finset.sum_congr,Finset.card_eq_sum_oneshave hsum : (∑ e ∈ T.edgeFinset, Sym2.lift ⟨fun u v ↦ T.dist (id u) (id v), fun _ _ ↦ T.dist_comm⟩ e) = ∑ e ∈ T.edgeFinset, 1 := Finset.sum_congr rfl h_eq rw [hsum, ← Finset.card_eq_sum_ones]
The terminal-only binary tree routing optimum tbt_opt T equals |E(T)|.
By definition, tbt_opt T is the infimum of identity routing costs over subcubic trees on V. For the upper bound, T is itself a subcubic tree on V with identity routing cost |E(T)|, so the infimum is at most |E(T)|. For the lower bound, any candidate subcubic tree H on V is a tree and therefore connected, so by the lower-bound lemma its identity routing cost is at least |E(T)|. By antisymmetry, the infimum is exactly |E(T)|.
uses
le_antisymm,Nat.sInf_le,tbt_opt_eq_sn_opt_of_is_subcubic_cost_self_id,le_csInf,tbt_opt_eq_sn_opt_of_is_subcubic_cost_ge_card,Function.Embedding.reflclassical have _ := hn have h_opt : tbt_opt T = T.edgeFinset.card := by rw [tbt_opt] apply le_antisymm · apply Nat.sInf_le exact ⟨T, hT, tbt_opt_eq_sn_opt_of_is_subcubic_cost_self_id T⟩ · apply le_csInf · exact ⟨T.edgeFinset.card, ⟨T, hT, tbt_opt_eq_sn_opt_of_is_subcubic_cost_self_id T⟩⟩ · rintro c ⟨H, hH, rfl⟩ have hconn : H.Connected := hH.1.connected exact tbt_opt_eq_sn_opt_of_is_subcubic_cost_ge_card T H hconn (Function.Embedding.refl V)
The Steiner binary tree routing optimum tbt_sn_opt T equals |E(T)|.
Similarly, tbt_sn_opt T is the infimum of routing costs over embeddings into subcubic trees on arbitrary finite types W. Embedding T into itself via the identity map witnesses that the infimum is at most |E(T)|. Conversely, any candidate subcubic tree H on any type W is connected, so the lower-bound lemma ensures every embedding f : V ↪ W has routing cost at least |E(T)|. Thus |E(T)| is a lower bound, and by antisymmetry tbt_sn_opt T = |E(T)|.
uses
le_antisymm,Nat.sInf_le,Function.Embedding.refl,tbt_opt_eq_sn_opt_of_is_subcubic_cost_self_id,le_csInf,tbt_opt_eq_sn_opt_of_is_subcubic_cost_ge_cardhave h_sn : tbt_sn_opt T = T.edgeFinset.card := by rw [tbt_sn_opt] apply le_antisymm · apply Nat.sInf_le exact ⟨V, inferInstance, T, hT, Function.Embedding.refl V, tbt_opt_eq_sn_opt_of_is_subcubic_cost_self_id T⟩ · apply le_csInf · exact ⟨T.edgeFinset.card, ⟨V, inferInstance, T, hT, Function.Embedding.refl V, tbt_opt_eq_sn_opt_of_is_subcubic_cost_self_id T⟩⟩ · rintro c ⟨W, _, H, hH, f, rfl⟩ have hconn : H.Connected := hH.1.connected exact tbt_opt_eq_sn_opt_of_is_subcubic_cost_ge_card T H hconn f
tbt_opt T = tbt_sn_opt T.
Since both tbt_opt T and tbt_sn_opt T equal |E(T)|, they are equal to each other.
rw [h_opt, h_sn]
Quot.exists_rep- Every element of a quotient type is represented by at least one element of the underlying type.
Sym2.lift_mk- Evaluating a lifted symmetric function on an unordered pair s(a, b) equals the underlying function evaluated at (a, b).
SimpleGraph.mem_edgeFinset- An unordered pair belongs to the finite edge set of a graph if and only if it belongs to its edge set.
SimpleGraph.mem_edgeSet- An unordered pair s(v, w) is in the edge set of a graph if and only if v and w are adjacent.
Finset.card_eq_sum_ones- The cardinality of a finite set equals the sum of 1 over all of its elements.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i in a finite set, then the sum of f over the set is at most the sum of g.
SimpleGraph.dist_eq_one_iff_adj.mpr- If two vertices in a graph are adjacent, the shortest-path distance between them is 1.
Finset.sum_congr- Sums over equal finite sets of pointwise equal functions are equal.
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
Nat.sInf_le- In the natural numbers, the infimum of a set is less than or equal to any of its elements.
le_csInf- If a set is nonempty and a is a lower bound for every element of the set, then a ≤ sInf s.
Function.Embedding.refl- The identity function viewed as an injective embedding of a type into itself.
tbt_opt_eq_sn_opt_of_is_subcubic_cost_self_id- The routing cost of a graph T in itself under the identity map equals the number of edges of T.
tbt_opt_eq_sn_opt_of_is_subcubic_cost_ge_card- For any graph T and connected graph H, the routing cost of T in H under any embedding f is at least the number of edges of T.
- The hypothesis hn that |V| ≥ 2 is declared in the theorem signature and recorded at line 37, but it is not used in the proof.
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.
open Classical inlemma tbt_opt_eq_sn_opt_of_is_subcubic_cost_ge_card {V W : Type*} [Fintype V] (T : SimpleGraph V) (H : SimpleGraph W) (hH : H.Connected) (f : V ↪ W) : T.edgeFinset.card ≤ tree_routing_cost T H f := by rw [tree_routing_cost] have h_le : ∀ e ∈ T.edgeFinset, 1 ≤ Sym2.lift ⟨fun u v ↦ H.dist (f u) (f v), fun _ _ ↦ H.dist_comm⟩ e := by intro e he obtain ⟨⟨u, v⟩, rfl⟩ := Quot.exists_rep e simp only [Sym2.lift_mk] rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he have hne : u ≠ v := T.ne_of_adj he have hne' : f u ≠ f v := f.injective.ne hne exact hH.pos_dist_of_ne hne' have hcard : T.edgeFinset.card = ∑ e ∈ T.edgeFinset, 1 := Finset.card_eq_sum_ones T.edgeFinset rw [hcard] exact Finset.sum_le_sum h_leopen Classical inlemma tbt_opt_eq_sn_opt_of_is_subcubic_cost_self_id {V : Type*} [Fintype V] (T : SimpleGraph V) : tree_routing_cost T T id = T.edgeFinset.card := by rw [tree_routing_cost] have h_eq : ∀ e ∈ T.edgeFinset, Sym2.lift ⟨fun u v ↦ T.dist (id u) (id v), fun _ _ ↦ T.dist_comm⟩ e = 1 := by intro e he obtain ⟨⟨u, v⟩, rfl⟩ := Quot.exists_rep e simp only [Sym2.lift_mk, id] rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] at he exact SimpleGraph.dist_eq_one_iff_adj.mpr he have hsum : (∑ e ∈ T.edgeFinset, Sym2.lift ⟨fun u v ↦ T.dist (id u) (id v), fun _ _ ↦ T.dist_comm⟩ e) = ∑ e ∈ T.edgeFinset, 1 := Finset.sum_congr rfl h_eq rw [hsum, ← Finset.card_eq_sum_ones]/-- For any demand tree that is already subcubic, the terminal-only and Steiner binary host routing optima are equal. -/theorem tbt_opt_eq_sn_opt_of_is_subcubic {V : Type} [Fintype V] (T : SimpleGraph V) (hT : is_subcubic_tree T) (hn : 2 ≤ Fintype.card V) : tbt_opt T = tbt_sn_opt T := by classical have _ := hn have h_opt : tbt_opt T = T.edgeFinset.card := by rw [tbt_opt] apply le_antisymm · apply Nat.sInf_le exact ⟨T, hT, tbt_opt_eq_sn_opt_of_is_subcubic_cost_self_id T⟩ · apply le_csInf · exact ⟨T.edgeFinset.card, ⟨T, hT, tbt_opt_eq_sn_opt_of_is_subcubic_cost_self_id T⟩⟩ · rintro c ⟨H, hH, rfl⟩ have hconn : H.Connected := hH.1.connected exact tbt_opt_eq_sn_opt_of_is_subcubic_cost_ge_card T H hconn (Function.Embedding.refl V) have h_sn : tbt_sn_opt T = T.edgeFinset.card := by rw [tbt_sn_opt] apply le_antisymm · apply Nat.sInf_le exact ⟨V, inferInstance, T, hT, Function.Embedding.refl V, tbt_opt_eq_sn_opt_of_is_subcubic_cost_self_id T⟩ · apply le_csInf · exact ⟨T.edgeFinset.card, ⟨V, inferInstance, T, hT, Function.Embedding.refl V, tbt_opt_eq_sn_opt_of_is_subcubic_cost_self_id T⟩⟩ · rintro c ⟨W, _, H, hH, f, rfl⟩ have hconn : H.Connected := hH.1.connected exact tbt_opt_eq_sn_opt_of_is_subcubic_cost_ge_card T H hconn f rw [h_opt, h_sn]