AFTD Auto-Formalizing Theoretical Domains

tbt_opt_eq_sn_opt_of_is_subcubic

theoremverified

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)|.

  1. 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.

    lines 5–13

    uses Quot.exists_rep, Sym2.lift_mk, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet

      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'
  2. 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)|.

    lines 14–16

    uses Finset.card_eq_sum_ones, Finset.sum_le_sum

      have hcard : T.edgeFinset.card = ∑ e ∈ T.edgeFinset, 1 := Finset.card_eq_sum_ones T.edgeFinset
      rw [hcard]
      exact Finset.sum_le_sum h_le
  3. 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.

    lines 21–27

    uses Quot.exists_rep, Sym2.lift_mk, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, SimpleGraph.dist_eq_one_iff_adj.mpr

      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
  4. 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)|.

    lines 28–30

    uses Finset.sum_congr, Finset.card_eq_sum_ones

      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]
  5. 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)|.

    lines 36–47

    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.refl

      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)
  6. 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)|.

    lines 48–57

    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_card

      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
  7. 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.

    line 58

      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.

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

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]
See it in the graphDiscuss this resultChallenge it