§3, p. 389 — a minimal T-join is the edge-disjoint union of |T|/2 paths pairing the vertices of T
ProvedMetricGenerators.ConnectedJoin.minimal_tjoin_pathsgraph-theoryp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pathst-join
Let be a connected finite graph, let have even cardinality, and let be an inclusionwise minimal -join of . Put . Then the vertices of can be listed as distinct vertices , and there are paths in , joining and , such that
The paper records this fact at the start of §3 and uses it in the sufficiency half of Lemma 2, applied to a minimum -join.
Formalization Note. "Minimal" is inclusionwise minimality and "disjoint" is edge-disjoint, as the paper restates it on p. 392. The pairing is encoded as an injective map from two copies of to whose image is ; the paths are Walks of that are paths.
Preamble
import Mathlib import Definitions.Def_MetricGenerators_ConnectedJoin_TJoin
Formal statement
namespace MetricGenerators.ConnectedJoin
/-- **§3, p. 389 (unnumbered).** "It is useful to know and easy to check that a minimal T-join is
the disjoint union of |T|/2 paths pairing the vertices of T." (Sebő and Tannier, On Metric
Generators of Graphs, Math. Oper. Res. 29(2):383–393 (2004), DOI 10.1287/moor.1030.0070, p. 389.)
Let `G` be a connected graph, `T` a vertex set of even cardinality and `F` an inclusionwise
minimal `T`-join. With `m = |T|/2`, there are vertices `s i, t i` (`i < m`), all `2m` of them
distinct and together forming `T`, and paths `P i` of `G` from `s i` to `t i`, pairwise
edge-disjoint, whose edges together are exactly `F`.
**Formalization Note.** "Minimal" is inclusionwise minimality (`IsMinimalTJoin`); "disjoint" is
edge-disjoint (as p. 392 restates it: "J is the edge-disjoint union of m := |T|/2 paths"). The
pairing is the injective map `Sum.elim s t : Fin m ⊕ Fin m → V` with range `T`. -/
theorem minimal_tjoin_paths {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
(hG : G.Connected) (T : Finset V) (hT : Even T.card) (F : Finset (Sym2 V))
(hF : IsMinimalTJoin G T F) :
∃ (s t : Fin (T.card / 2) → V) (P : ∀ i, G.Walk (s i) (t i)),
Function.Injective (Sum.elim s t) ∧
Set.range (Sum.elim s t) = (↑T : Set V) ∧
(∀ i, (P i).IsPath) ∧
(∀ i j, i ≠ j → Disjoint (P i).edges.toFinset (P j).edges.toFinset) ∧
Finset.univ.biUnion (fun i => (P i).edges.toFinset) = F := 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. 389, §3 (unnumbered)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.