Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 6, p. 392 — the image F of the tree A under the isometry is a T-join and a tree with μ_F = μ_G on V(F)

Proved
MetricGenerators.ConnectedJoin.image_of_realization

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 T⊆V(G)T\subseteq V(G)T⊆V(G) nonempty. Let AAA be a tree, g:T→V(A)g:T\to V(A)g:T→V(A) a map, and T′=g(T)T'=g(T)T′=g(T). Suppose

  1. AAA is a T′T'T′-join: a vertex of AAA has odd degree in AAA exactly when it lies in T′T'T′;
  2. φ:V(A)→V(G)\varphi:V(A)\to V(G)φ:V(A)→V(G) is an isometry from AAA to GGG, i.e. μG(φ(a),φ(b))=dA(a,b)\mu_G(\varphi(a),\varphi(b))=d_A(a,b)μG​(φ(a),φ(b))=dA​(a,b) for all a,ba,ba,b, extending the inverse of ggg: φ(g(t))=t\varphi(g(t))=tφ(g(t))=t for all t∈Tt\in Tt∈T.

Let F={φ(a)φ(b):ab∈E(A)}F=\{\varphi(a)\varphi(b): ab\in E(A)\}F={φ(a)φ(b):ab∈E(A)} be the image of AAA in GGG. Then

F is a T-join of G,F is a tree,μF(x,y)=μG(x,y) for all x,y∈V(F).F\ \text{is a }T\text{-join of }G,\qquad F\ \text{is a tree},\qquad \mu_F(x,y)=\mu_G(x,y)\ \text{for all }x,y\in V(F).F is a T-join of G,F is a tree,μF​(x,y)=μG​(x,y) for all x,y∈V(F).

In the proof of Theorem 6 these are exactly the hypotheses of Lemma 2, which then shows that FFF is a connected minimum TTT-join.

Formalization Note. "f:T′→Tf:T'\to Tf:T′→T is the inverse of ggg" and "φ\varphiφ extends fff" are encoded together as φ(g(t))=t\varphi(g(t))=tφ(g(t))=t. It is not assumed that ggg realizes μG∣T\mu_G|_TμG​∣T​; that follows from the other hypotheses. The hypothesis T≠∅T\neq\emptysetT=∅ is the one Theorem 6 carries: for T=∅T=\emptysetT=∅ the tree AAA may be a single vertex, and then F=∅F=\emptysetF=∅ is not a tree.

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

/-- **Proof of Theorem 6, p. 392 (unnumbered).** "Let F be the image of A in G provided by the
isometry of the third condition. Then by the second condition, F is a T-join, and since it is a
tree, it is connected. Now we see from this construction that the condition of Lemma 2 is
satisfied: μ_F arises from μ_G|T by two isometries." (Sebő and Tannier, On Metric Generators of
Graphs, Math. Oper. Res. 29(2):383–393 (2004), DOI 10.1287/moor.1030.0070, p. 392.)

Let `G` be a connected graph, `T` a nonempty vertex set, `A` a tree on `Fin N`, `g : T → V(A)`,
and suppose `A` is a `g(T)`-join and `φ : V(A) → V(G)` is an isometry from `A` to `G` extending
the inverse of `g` (`φ (g t) = t`). Let `F` be the image of the edges of `A` under `φ`. Then `F`
is a `T`-join of `G`, the graph `(V(F), F)` is a tree, and the distance in `(V(F), F)` between any
two vertices of `V(F)` equals their distance in `G`.

**Formalization Note.** "Isometry from A to G" is distance preservation for all pairs of vertices
of `A`. "f is the inverse of g" and "extending f" are encoded together as `φ (g t) = t`. The
hypothesis `T.Nonempty` is the standing nonemptiness of Theorem 6 (see `theorem_6`); without it
`A` may be a single vertex and `F = ∅`, which is not a tree. That `g` realizes μ_G|T is not
assumed: it follows from the isometry and `φ (g t) = t`. -/
theorem image_of_realization {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    (hG : G.Connected) (T : Finset V) (hT : T.Nonempty) {N : ℕ} (A : SimpleGraph (Fin N))
    [DecidableRel A.Adj] (hA : A.IsTree) (g : ↥T → Fin N) (hjoin : GraphIsJoin A (Set.range g))
    (φ : Fin N → V) (hφ : ∀ a b : Fin N, G.dist (φ a) (φ b) = A.dist a b)
    (hext : ∀ t : ↥T, φ (g t) = ↑t) :
    MetricGenerators.FewComponents.IsTJoin G T (A.edgeFinset.image (Sym2.map φ)) ∧
      IsTreeEdgeSet (A.edgeFinset.image (Sym2.map φ)) ∧
      ∀ x ∈ MetricGenerators.FewComponents.edgeSupport (A.edgeFinset.image (Sym2.map φ)),
        ∀ y ∈ MetricGenerators.FewComponents.edgeSupport (A.edgeFinset.image (Sym2.map φ)),
          edgeDist (A.edgeFinset.image (Sym2.map φ)) x y = G.dist x y := 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, §3.2, proof of Theorem 6 (unnumbered)
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