Contractible realizations of finite trees
Consulted manifestations, attribution and rights: ReebOrdering-aa7d10f, mathlib-0df444a.
This digest builds on the realization of simple graphs in reeb-graph-realization.md and on the necessary tree condition in reeb-graph-cycle-obstruction.md. It proves the converse for finite vertex types: the realization of a finite tree is contractible. Hence a graph on a finite vertex type is a tree exactly when its realization is simply connected, and exactly when it is contractible.
Removing a leaf
For V : Type u, G : SimpleGraph V and a vertex ℓ, the embedding of the induced graph
G.induce {ℓ}ᶜ gives
deleteVertexInclusion G ℓ : C(Realization (G.induce {ℓ}ᶜ), Realization G)
deleteVertexInclusion G ℓ (vertex _ v) = vertex G v
deleteVertexInclusion G ℓ (edgePoint _ d t) = edgePoint G ⟨(d.fst, d.snd), d.adj⟩ t
Let ℓ be a leaf with neighbour m: hadj : G.Adj ℓ m and huniq : ∀ w, G.Adj ℓ w → w = m.
The leaf collapse is
leafCollapse hadj huniq : C(Realization G, Realization (G.induce {ℓ}ᶜ))
leafCollapse (vertex G ℓ) = vertex _ m
leafCollapse (vertex G v) = vertex _ v -- v ≠ ℓ
leafCollapse (edgePoint G d t) = edgePoint _ d t -- d.fst ≠ ℓ, d.snd ≠ ℓ
leafCollapse (edgePoint G d t) = vertex _ m -- d.fst = ℓ or d.snd = ℓ
(leafCollapse_vertex_self, leafCollapse_vertex_of_ne, leafCollapse_edgePoint_of_ne,
leafCollapse_edgePoint_of_eq). A dart touching ℓ is ℓ → m or m → ℓ, so the start equation
of the lift holds on both. Collapsing after including is the identity
(leafCollapse_comp_deleteVertexInclusion, by hom_ext).
Including after collapsing is homotopic to the identity by the leaf slide. At time s,
leafHomotopy (s, vertex G ℓ) = edgePoint G (ℓ → m) s
leafHomotopy (s, vertex G v) = vertex G v -- v ≠ ℓ
leafHomotopy (s, edgePoint G d t) = edgePoint G d (1 - (1 - t)(1 - s)) -- d.fst = ℓ
leafHomotopy (s, edgePoint G d t) = edgePoint G d (t (1 - s)) -- d.snd = ℓ
leafHomotopy (s, edgePoint G d t) = edgePoint G d t -- otherwise
(leafHomotopy_vertex_self, leafHomotopy_vertex_of_ne, leafHomotopy_edgePoint_of_fst_eq,
leafHomotopy_edgePoint_of_snd_eq, leafHomotopy_edgePoint_of_ne). The two leaf-edge formulas
agree under reversal: the point of m → ℓ at (1 - t)(1 - s) is the point of ℓ → m at
1 - (1 - t)(1 - s). At t = 0 they give the track of ℓ and the fixed vertex m.
At s = 0 every formula is the identity; at s = 1 the leaf edge and ℓ are at m, which is the collapse followed by the
inclusion. The dart leaving the leaf is determined by huniq, while the two cases are told apart by
d.fst = ℓ and d.snd = ℓ alone, which cannot both hold.
Continuity: the vertex tracks and the curried edge tracks are continuous maps into
C(unitInterval, Realization G) satisfying the reversal and start equations, so the bundled lift
continuousLift is a continuous map Realization G → C(unitInterval, Realization G). Since the
unit interval is locally compact, its uncurried form is continuous on
Realization G × unitInterval (ContinuousMap.continuous_uncurry_of_continuous). No statement
that a product of the quotient map with the unit interval is a quotient map is used.
The result is leafHomotopyEquiv hadj huniq : Realization G ≃ₕ Realization (G.induce {ℓ}ᶜ) with
forward map the collapse and inverse the inclusion. The leaf step assumes no finiteness.
Finite trees
contractibleSpace_realization_of_isTree [Finite V] : G.IsTree → ContractibleSpace (Realization G)
simplyConnectedSpace_realization_of_isTree [Finite V] : G.IsTree → SimplyConnectedSpace (Realization G)
isTree_iff_simplyConnectedSpace_realization [Finite V] : G.IsTree ↔ SimplyConnectedSpace (Realization G)
isTree_iff_contractibleSpace_realization [Finite V] : G.IsTree ↔ ContractibleSpace (Realization G)
The first is proved for every V : Type u with n + 1 elements by induction on n. With one
vertex there is no edge, since a dart would join a vertex to itself, so the realization is a single
point. With at least two vertices, a finite tree has a vertex ℓ of degree one
(SimpleGraph.IsTree.exists_ne_and_degree_eq_one, with the edge-set finiteness and local
finiteness obtained classically from Finite V), whose neighbour m is unique
(SimpleGraph.degree_eq_one_iff_existsUnique_adj). The graph induced on {ℓ}ᶜ is connected
(SimpleGraph.Connected.induce_compl_singleton_of_degree_eq_one) and acyclic
(SimpleGraph.IsAcyclic.induce), hence a tree, on n vertices
(Set.ncard_compl_of_ncard_eq_add). Contractibility transfers back along the leaf homotopy
equivalence (ContinuousMap.HomotopyEquiv.contractibleSpace). A contractible space is simply
connected (SimplyConnectedSpace.ofContractible), and the reverse directions are the necessary
condition isTree_of_simplyConnectedSpace, which assumes no finiteness.
The hypothesis is [Finite V]; decidability and Fintype instances are chosen inside the proof.
Every vertex of a tree with at least two vertices lies on an edge, so a tree with finitely many
edges has finitely many vertices, and assuming only a finite edge set would cover no further trees.
Names and universes
The results live in namespace TDA.Reeb.GraphTreeContraction (TDA/Reeb/GraphTreeContraction.lean)
and the fixtures in TDA.Reeb.Examples.GraphTreeContraction
(TDA/Reeb/GraphTreeContractionExamples.lean). The vertex type has an arbitrary universe u. The
graph is explicit in deleteVertexInclusion and the tree theorems and implicit, through hadj, in
the collapse, the slide and the equivalence. The cellwise data of the collapse and the slide are
private.
Fixtures
The module TDA/Reeb/GraphTreeContractionExamples.lean proves:
- Empty vertex type. For every
[IsEmpty V]the realization is not contractible (empty_not_contractibleSpace). Withempty_not_isTreeandempty_not_simplyConnectedSpaceof the cycle-obstruction fixtures, both criteria hold with both sides false. - One vertex. The realization of the one-vertex graph is contractible by the finite-tree
theorem, from
SimpleGraph.IsTree.of_subsingleton(point_contractibleSpace). - Path on three vertices.
pathGraph 3equals the star centred at1, so it is a tree (path3_eq_starGraph,path3_isTree), and its realization is contractible and simply connected (path3_contractibleSpace,path3_simplyConnectedSpace). The vertex0is a leaf with neighbour1(path3_adj_01,path3_eq_one_of_adj_zero). Its leaf steppath3LeafEquivslides0along the dart0 → 1, shortens that dart, and fixes the vertex2and the edge1 — 2(path3_slide_leaf,path3_slide_d01,path3_slide_two,path3_slide_d12); the collapse sends0to1(path3_collapse_leaf). Through the equivalence the remaining edge1 — 2has contractible realization (path3_remainder_contractibleSpace). - Star with three leaves. For
star4 = starGraph (0 : Fin 4)the realization is contractible and, through the tree criterion, simply connected (star4_contractibleSpace,star4_simplyConnectedSpace). - Triangle. The triangle
⊤ : SimpleGraph (Fin 3)is not a tree (triangle_not_isTreeof the cycle-obstruction fixtures), so by the two criteria its realization is neither simply connected nor contractible (triangle_not_simplyConnectedSpace,triangle_not_contractibleSpace).
Source correspondence
Source. The leaf collapse, the leaf slide, the leaf homotopy equivalence and the induction on
the number of vertices are adapted from uda-lab/reeb-ordering,
ReebOrdering/GraphRealisation.lean
at commit aa7d10f4f7dc0474b76f17ea81afcab5a230d521 (blob
6b79160f368a9d6fd63f2d52f1db4d9c5697cfa8), Copyright 2026 Tomoki Uda, licensed under the
Apache License, Version 2.0.
The source is not imported and is not a dependency.
| Library declaration | Source declaration | Lines |
|---|---|---|
deleteVertexInclusion |
leafIncl |
473–474 |
leafCollapse and its evaluation lemmas |
leafCollapse, leafCollapseVertex, leafCollapseEdge and their lemmas |
388–491 |
leafCollapse_comp_deleteVertexInclusion |
leafCollapse_comp_leafIncl |
498–527 |
leafHomotopy |
leafDart, leafHomotopy, leafHomotopyVertex, leafHomotopyEdge and their lemmas |
372–386, 529–738 |
leafHomotopyEquiv |
leafHomotopyEquiv |
740–748 |
contractibleSpace_realization_of_isTree |
contractibleSpace_realisation_of_isTree |
750–799 |
simplyConnectedSpace_realization_of_isTree |
simplyConnectedSpace_of_isTree |
801–804 |
isTree_iff_simplyConnectedSpace_realization |
SimpleGraph.isTree_iff_simplyConnectedSpace_realisation |
812–815 |
Changes: the names; public visibility of the inclusion, collapse, slide and equivalence; the leaf
dart oriented away from the leaf (the source's leafDart is m → ℓ) and the edge tracks chosen by
whether a dart leaves or enters the leaf, rather than by equality with the leaf dart; continuity of
the slide through curried edge tracks and continuousLift, in place of the source's liftProd and
continuous_liftProd (112–153), which rest on a product-of-quotient-maps lemma that neither this
library nor pinned mathlib provides; the induction stated for n + 1 vertices; and the necessary
direction from isTree_of_simplyConnectedSpace
(reeb-graph-cycle-obstruction.md).
isTree_iff_contractibleSpace_realization, the evaluation lemmas of the inclusion and the slide,
and every fixture are new. The source's Hasse-order result (817–830) is not ported.
Mathlib and TauCeti. Pinned mathlib has leaves of finite trees and connectedness after deleting
a leaf (Mathlib/Combinatorics/SimpleGraph/Acyclic.lean), contractible spaces and their transfer
along homotopy equivalences (Mathlib/Topology/Homotopy/Contractible.lean) and the instance from
contractible to simply connected, but no realization of simple graphs. The search of TauCeti
recorded in reeb-graph-realization.md applies with the same limits;
nothing from TauCeti is used.
Not claimed here: contractibility or simple connectivity of realizations of trees on infinite
vertex types, which leaf removal does not reach; for example starGraph (0 : ℕ) is a tree to which
these theorems do not apply. Also not claimed: fundamental groups of realizations of graphs with
cycles; Hasse-order results.
Sources: pinned mathlib acyclic graphs, contractible spaces, simply connected spaces and the compact-open uncurrying.