Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§2, p. 387 — the C^(0)_u are pairwise disjoint and C^(0)_t = {f(t)} for t ∈ T

Proved
MetricGenerators.IsometryExt.initial_candidates

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, T⊆V(H)T\subseteq V(H)T⊆V(H) a metric generator of HHH, and f:(T,μH∣T)→Gf:(T,\mu_H|_T)\to Gf:(T,μH​∣T​)→G an isometry. Let Cu(0)={v∈V(G):μG(f(t),v)=μH(t,u) ∀t∈T}C^{(0)}_u=\{v\in V(G):\mu_G(f(t),v)=\mu_H(t,u)\ \forall t\in T\}Cu(0)​={v∈V(G):μG​(f(t),v)=μH​(t,u) ∀t∈T} be the initial candidate sets. Then

  1. Cu(0)∩Cv(0)=∅C^{(0)}_u\cap C^{(0)}_v=\emptysetCu(0)​∩Cv(0)​=∅ whenever u≠vu\ne vu=v;
  2. Ct(0)={f(t)}C^{(0)}_t=\{f(t)\}Ct(0)​={f(t)} for every t∈Tt\in Tt∈T.

These are the first observations about the candidate procedure: the candidates for distinct vertices never collide, and the vertices of TTT have exactly their prescribed image as candidate.

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, §2, p. 387 (unnumbered): as `T` is a metric generator of `H`, the initial candidate
sets `C^(0)_u` (`u ∈ V(H)`) are pairwise disjoint; using also that `f` is an isometry on `T`,
`C^(0)_t = {f(t)}` for every `t ∈ T`.

Formalization Note: `H` and `G` are finite and connected (standing assumption, p. 383). The page
invokes only the metric-generator property of `T`, which is the hypothesis used here. -/
theorem initial_candidates {VH VG : Type*} [Fintype VH] [Fintype VG]
    (H : SimpleGraph VH) (G : SimpleGraph VG) (hH : H.Connected) (hG : G.Connected)
    (T : Finset VH) (hT : IsMetricGenerator H T) (f : ↥T → VG) (hf : IsIsometryOn H G T f) :
    (∀ u v : VH, u ≠ v → Disjoint (cand H G T f 0 u) (cand H G T f 0 v)) ∧
    (∀ t : ↥T, cand H G T f 0 t = {f t}) := 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, §2 (unnumbered, after the definition of C^(0)_u)
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