Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1, p. 387 — in a representation, μ_H(u, v) = μ_G(x, C_v) for every x ∈ C_u

Proved
MetricGenerators.IsometryExt.lemma_1

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

graph-isometrygraph-theorymetric-generatorp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let HHH and GGG be finite connected graphs, TTT a strong metric generator of HHH, f:(T,μH∣T)→Gf:(T,\mu_H|_T)\to Gf:(T,μH​∣T​)→G an isometry, and let nonempty sets CuC_uCu​ (u∈V(H)u\in V(H)u∈V(H)) represent HHH in GGG with respect to TTT. Then for all u,v∈V(H)u,v\in V(H)u,v∈V(H) and every x∈Cux\in C_ux∈Cu​,

μH(u,v)=μG(x,Cv):=min⁡{μG(x,y): y∈Cv}.\mu_H(u,v)=\mu_G(x,C_v):=\min\{\mu_G(x,y):\ y\in C_v\}.μH​(u,v)=μG​(x,Cv​):=min{μG​(x,y): y∈Cv​}.

The lemma is the intermediate stage between a representation and an isometry: each candidate for uuu sits at exactly the right distance from the candidate set of every other vertex.

Formalization Note The minimum is stated as two facts: some y∈Cvy\in C_vy∈Cv​ has μG(x,y)=μH(u,v)\mu_G(x,y)=\mu_H(u,v)μG​(x,y)=μH​(u,v), and every y∈Cvy\in C_vy∈Cv​ has μH(u,v)≤μG(x,y)\mu_H(u,v)\le\mu_G(x,y)μH​(u,v)≤μG​(x,y). No forest hypothesis is needed.

Preamble
import Mathlib
import Definitions.Def_MetricGenerators_IsometryExt_Basic
import Definitions.Def_MetricGenerators_IsometryExt_Representation
Formal statement
namespace MetricGenerators.IsometryExt

/-- Sebő and Tannier, *On Metric Generators of Graphs*, Math. Oper. Res. 29(2):383–393 (2004),
DOI 10.1287/moor.1030.0070, p. 387, **Lemma 1**: if nonempty sets `C_u` represent `H` in `G` with respect to the
strong metric generator `T`, then for all `u, v ∈ V(H)` and `x ∈ C_u`, `μ_H(u, v) = μ_G(x, C_v)`,
where `μ_G(x, C_v) = min {μ_G(x, y) : y ∈ C_v}`.

Formalization Note: the minimum is encoded as "attained and a lower bound": some `y ∈ C_v` has
`μ_G(x, y) = μ_H(u, v)`, and every `y ∈ C_v` has `μ_H(u, v) ≤ μ_G(x, y)` (no `sInf` on `ℕ`).
There is no forest hypothesis: the lemma holds for every strong metric generator. -/
theorem lemma_1 {VH VG : Type*} [Fintype VH] [Fintype VG]
    (H : SimpleGraph VH) (G : SimpleGraph VG) (hH : H.Connected) (hG : G.Connected)
    (T : Finset VH) (hT : IsStrongMetricGenerator H T) (f : ↥T → VG)
    (hf : IsIsometryOn H G T f) (C : VH → Set VG) (hC : Represents H G T f C) :
    ∀ u v : VH, ∀ x ∈ C u,
      (∃ y ∈ C v, G.dist x y = H.dist u v) ∧ (∀ y ∈ C v, H.dist u v ≤ G.dist x y) := by sorry

end MetricGenerators.IsometryExt
Source
Sebő and Tannier, On Metric Generators of Graphs, Math. Oper. Res. 29(2):383–393 (2004), DOI 10.1287/moor.1030.0070, p. 387, Lemma 1 (proof p. 388); μ_G(X, Y) defined on p. 387
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