Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6 — a connected minimum T-join exists iff μ_G|T is a tree metric whose minimal realization A is a T′-join and embeds isometrically in G extending f

Proved
MetricGenerators.ConnectedJoin.theorem_6

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

isometric-embeddingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1t-jointree-metric

Let GGG be a connected finite graph and let T⊆V(G)T\subseteq V(G)T⊆V(G) be a nonempty set of vertices of even cardinality. Write μG\mu_GμG​ for the shortest-path distance of GGG and μG∣T\mu_G|_TμG​∣T​ for its restriction to TTT. Then GGG has a TTT-join that is both minimum and connected if and only if all of the following hold:

  1. μG∣T\mu_G|_TμG​∣T​ is a tree metric; let AAA be its (inclusionwise) minimal realization, ggg the isometry from (T,μG∣T)(T,\mu_G|_T)(T,μG​∣T​) to AAA, T′=g(T)T'=g(T)T′=g(T), and f:T′→Tf:T'\to Tf:T′→T the inverse of ggg;
  2. the tree AAA is a T′T'T′-join, i.e. a vertex of AAA has odd degree exactly when it lies in T′T'T′;
  3. there is an isometry φ\varphiφ from AAA to GGG extending fff:
μG(φ(a),φ(b))=dA(a,b)  for all a,b∈V(A),φ(g(t))=t  for all t∈T.\mu_G\bigl(\varphi(a),\varphi(b)\bigr)=d_A(a,b)\ \ \text{for all }a,b\in V(A),\qquad \varphi\bigl(g(t)\bigr)=t\ \ \text{for all }t\in T.μG​(φ(a),φ(b))=dA​(a,b)  for all a,b∈V(A),φ(g(t))=t  for all t∈T.

The theorem reduces the existence of a connected minimum TTT-join to a property of the metric μG∣T\mu_G|_TμG​∣T​ alone (conditions 1 and 2) plus an isometric embedding problem for a tree. In particular, if the minimal realization of μG∣T\mu_G|_TμG​∣T​ exists but is not a T′T'T′-join, no minimum TTT-join is connected.

Formalization Note. Conditions 2 and 3 are required of every inclusionwise minimal realization (A,g)(A,g)(A,g); all of them are isomorphic by isomorphisms respecting ggg, so this is the paper's "AAA denotes its unique minimal realization". The hypothesis T≠∅T\neq\emptysetT=∅ is added: for T=∅T=\emptysetT=∅ the only minimum TTT-join is ∅\emptyset∅, whose connectivity is a convention the paper does not discuss (with the convention used here, a connected graph has a vertex). Distances are natural numbers. A realization is a tree on Fin N\mathrm{Fin}\,NFinN. A TTT-join is connected when the graph (V(F),F)(V(F),F)(V(F),F) is connected.

Preamble
import Mathlib
import Definitions.Def_MetricGenerators_ConnectedJoin_TJoin
import Definitions.Def_MetricGenerators_ConnectedJoin_TreeMetric
Formal statement
namespace MetricGenerators.ConnectedJoin

/-- **Theorem 6** (p. 392). "Let G be a connected graph, and let T be a subset of vertices of even
cardinality. There exists a connected minimum T-join in G if and only if all of the following
conditions hold:
• μ_G|T is a tree metric, A denotes its unique minimal realization, and g is the isometry from
(T, μ_G|T) to A, T′ := g(T); f : T′ → T is the inverse of g;
• The tree A is a T′-join;
• There exists an isometry from A to G extending f."
(Sebő and Tannier, On Metric Generators of Graphs, Math. Oper. Res. 29(2):383–393 (2004),
DOI 10.1287/moor.1030.0070, p. 392, Theorem 6.)

Let `G` be a connected finite graph and `T` a nonempty vertex set of even cardinality. There is a
`T`-join of `G` that is minimum and connected if and only if μ_G|T is a tree metric and, for every
inclusionwise minimal realization `(A, g)` of μ_G|T, (i) `A` is a `g(T)`-join and (ii) there is an
isometry `φ` from `A` to `G` with `φ (g t) = t` for every `t ∈ T`.

**Formalization Note.**
* "A denotes its unique minimal realization" is read as "for the minimal realization": conditions
  (i) and (ii) are required of **every** inclusionwise minimal realization. All of them are
  isomorphic by isomorphisms commuting with the realization maps (`minimal_realization_unique`),
  so this is the same as requiring them of one; but requiring them of *some* minimal realization
  would be a different reading in which the necessity half does not need the uniqueness.
* "f is the inverse of g" and "an isometry from A to G extending f" are encoded together as
  `φ (g t) = t`; an isometry preserves all distances.
* Added hypothesis `T.Nonempty`: for `T = ∅` the only minimum `T`-join is `∅`, whose
  connectivity is a convention the paper does not discuss; with Mathlib's convention (a connected
  graph has a vertex) the left side would be false and the right side true.
* Distances are `ℕ`-valued graph distances (`SimpleGraph.dist`); realizations are trees on `Fin N`
  (see `IsRealization`). Connectivity of `F` is connectivity of the graph `(V(F), F)`. -/
theorem theorem_6 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (hG : G.Connected)
    (T : Finset V) (hT : Even T.card) (hTne : T.Nonempty) :
    (∃ F : Finset (Sym2 V), MetricGenerators.FewComponents.IsMinTJoin G T F ∧ IsConnectedEdgeSet F) ↔
      (IsTreeMetric (fun s t : ↥T => G.dist ↑s ↑t) ∧
        ∀ (N : ℕ) (A : SimpleGraph (Fin N)) (g : ↥T → Fin N),
          IsMinimalRealization (fun s t : ↥T => G.dist ↑s ↑t) A g →
            GraphIsJoin A (Set.range g) ∧
              ∃ φ : Fin N → V, (∀ a b : Fin N, G.dist (φ a) (φ b) = A.dist a b) ∧
                ∀ t : ↥T, φ (g t) = ↑t) := by sorry

end MetricGenerators.ConnectedJoin
Source
Sebő and Tannier, On Metric Generators of Graphs, Math. Oper. Res. 29(2):383–393 (2004), DOI 10.1287/moor.1030.0070, p. 392, Theorem 6
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me