Realizations of simple graphs

Consulted manifestations, attribution and rights: ReebOrdering-aa7d10f, mathlib-0df444a.

The realization

For V : Type u and G : SimpleGraph V the cells are

Cells G = V ⊕ Σ _ : G.Dart, unitInterval

one point for each vertex and one copy of the unit interval for each dart, that is, for each oriented edge. The vertex summand carries the discrete topology ⊥, whatever topology V may have, and the edge summand the sigma (disjoint-union) topology of copies of the unit interval; each vertex cell is open (isOpen_vertexCell). The relation CellRel G has exactly two generators,

CellRel.symm d t  : (d, t) ~ (d.symm, σ t)
CellRel.start d   : (d, 0) ~ d.fst

orientation reversal and attachment of the start of a dart. Realization G := Quot (CellRel G) carries the quotient topology, with quotient map quotMk. Two cells have the same image exactly when the equivalence relation generated by CellRel G relates them (quotMk_eq_quotMk_iff, with Relation.EqvGen). The realization is neither given the discrete topology nor replaced by a quotient by components.

vertex G v and edgePoint G d t are the images of the cells. Reversal gives edgePoint G d.symm (σ t) = edgePoint G d t (edgePoint_symm); the start equation is edgePoint G d 0 = vertex G d.fst (edgePoint_zero), and the end equation edgePoint G d 1 = vertex G d.snd (edgePoint_one) follows from the two. Every point is a vertex or an edge point (ind), so functions and continuous maps out of the realization are determined by their values on vertices and edge points (function_ext, hom_ext). function_ext is not named funext, so opening the namespace does not shadow _root_.funext.

No finiteness, local finiteness, nonemptiness, decidable adjacency, separation or topology of the vertex type is assumed anywhere in the construction, the universal property, the maps or the component equivalence.

Universal property

Vertex data fv : V → Y and edge data fe : G.Dart → unitInterval → Y with

hsymm  : ∀ d t, fe d.symm (σ t) = fe d t
hstart : ∀ d, fe d 0 = fv d.fst

descend to lift G fv fe hsymm hstart : Realization G → Y, with lift_vertex and lift_edgePoint by rfl. The lift is unique among all functions with these values (lift_unique). It is continuous as soon as every fe d is (continuous_lift): continuity is checked through the quotient map, on the discrete vertex summand and on each interval cell separately; no topology on V is involved. For continuous edge data fe : G.Dart → C(unitInterval, Y), continuousLift : C(Realization G, Y) is the bundled form, with its evaluation lemmas, uniqueness among continuous maps (continuousLift_unique) and existsUnique_continuousLift.

Distinct vertices stay distinct (vertex_injective). The proof is set-level: the lift to Option V sending a vertex to itself, an endpoint of an edge to its vertex and an interior edge point to none respects both generators. No continuous retraction to the vertices is asserted. The realization is empty for an empty vertex type and nonempty for a nonempty one (instIsEmptyRealization, instNonemptyRealization).

Paths

edgePath G d : Path (vertex G d.fst) (vertex G d.snd) is the edge map on [0, 1] (edgePath_apply), and walkPath G p concatenates the edge paths of a walk p (walkPath_nil, walkPath_cons). Hence reachable vertices have joined images (joined_vertex_of_reachable). Every edge point is joined to the first endpoint of its dart (joined_edgePoint_vertex), by the straight path from t to 0 in the unit interval followed by the edge map. For any parameters s t : unitInterval, edgeSegment G d s t is the subpath from edgePoint G d s to edgePoint G d t. Its value at r is the edge point at Set.Icc.convexComb s t r (edgeSegment_apply); the endpoint laws are edgeSegment_zero and edgeSegment_one. This provides paths along one dart and says nothing about decomposing arbitrary paths into dart segments. The construction is Mathlib's Path.subpath applied to edgePath G d.

Maps induced by graph homomorphisms

For V : Type u, W : Type v and a graph homomorphism φ : G →g H,

realizationMap φ : C(Realization G, Realization H)
realizationMap φ (vertex G v)      = vertex H (φ v)
realizationMap φ (edgePoint G d t) = edgePoint H (φ.mapDart d) t

both formulas by rfl. It is the bundled lift of these data; the two compatibilities hold because φ.mapDart commutes with reversal and with the first endpoint. Identity and composition hold as equalities of continuous maps (realizationMap_id, realizationMap_comp), with three independent vertex universes for composition. A graph homomorphism preserves adjacency, so every edge goes to an edge and no edge is collapsed to a vertex. Nonadjacent vertices and distinct edges may be identified.

Path components

componentLabel G : Realization G → G.ConnectedComponent sends vertex G v to the component of v and edgePoint G d t to the component of d.fst; the two generators are respected because adjacent vertices lie in the same component. With the discrete topology chosen locally on the component type the label is continuous, so it is constant along paths (componentLabel_eq_of_joined, through TDA.Reeb.joined_eq_of_discrete). Hence two vertices have joined images exactly when they are reachable (joined_vertex_iff), and every edge point lies in the path component of a vertex (mk_edgePoint).

componentsEquiv G : ZerothHomotopy (Realization G) ≃ G.ConnectedComponent
componentsEquiv G (ZerothHomotopy.mk (vertex G v))         = G.connectedComponentMk v
componentsEquiv G (ZerothHomotopy.mk (edgePoint G d t))    = G.connectedComponentMk d.fst
(componentsEquiv G).symm (G.connectedComponentMk v)        = ZerothHomotopy.mk (vertex G v)

The forward map is the label on path components, and the inverse sends a graph component to the class of a representing vertex, well defined because walks give paths. All three formulas hold by rfl, and both inverse laws are fields of the equivalence: the vertex case is rfl and the edge case is mk_edgePoint.

Naturality. For every φ : G →g H and every path component c,

componentsEquiv H (TDA.Reeb.componentMap (realizationMap φ) c) = (componentsEquiv G c).map φ

(componentsEquiv_componentMap), where TDA.Reeb.componentMap is the library's map on ZerothHomotopy induced by a continuous map (see reeb-components.md) and the right-hand map is mathlib's SimpleGraph.ConnectedComponent.map. Both generator cases hold by rfl. The same square is available as an equation of functions (componentsEquiv_comp_componentMap) and in the inverse direction (componentMap_componentsEquiv_symm). The identity and composition laws of componentMap give componentMap (realizationMap Hom.id) = id (componentMap_realizationMap_id) and the composition law across three universes (componentMap_realizationMap_comp). No category of graphs is built.

Connectedness. connected_iff_pathConnectedSpace : G.Connected ↔ PathConnectedSpace (Realization G). Both sides include nonemptiness: mathlib's Connected carries Nonempty V, and PathConnectedSpace is equivalent to a nonempty subsingleton ZerothHomotopy (pathConnectedSpace_iff_zerothHomotopy). The proof transports both conditions along componentsEquiv; an empty graph is neither connected nor has a path-connected realization. The statement concerns path components, not connected components.

Library and mathlib declarations used

The production module uses the library declarations TDA.Reeb.componentMap, TDA.Reeb.componentMap_id and TDA.Reeb.componentMap_comp (TDA.Reeb.Components) and TDA.Reeb.joined_eq_of_discrete (TDA.Reeb.ComponentsDiscrete); the fixtures additionally use only TDA.Reeb.componentMap. None is restated. Its main pinned mathlib ingredients are SimpleGraph.ConnectedComponent with connectedComponentMk, lift, ind, exact, map and connectedComponentMk_eq_of_adj, SimpleGraph.Hom.mapDart, SimpleGraph.connected_iff, ZerothHomotopy with mk, lift, rec and sound, pathConnectedSpace_iff_zerothHomotopy, isQuotientMap_quot_mk, continuous_sum_dom and continuous_sigma; the fixtures also use SimpleGraph.ConnectedComponent.sound, SimpleGraph.pathGraph and SimpleGraph.reachable_bot.

Names and universes

The construction lives in namespace TDA.Reeb.GraphRealization (TDA/Reeb/GraphRealization.lean) and the fixtures in TDA.Reeb.Examples.GraphRealization (TDA/Reeb/GraphRealizationExamples.lean); no production module imports the fixtures. The vertex type has an arbitrary universe u, and Cells G and Realization G live in Type u. realizationMap, its laws, the naturality square and the corollaries allow independent universes for the vertex types of source, target and, for composition, a third graph; the same-universe case is an instance. The graph is an explicit argument of vertex, edgePoint, lift, continuousLift, componentsEquiv and the naturality square componentsEquiv_componentMap; realizationMap φ infers it from φ. The only private declaration is the straight path in the unit interval behind joined_edgePoint_vertex.

Fully qualified names are distinct from all other library names, but some short names are not. Realization, instTopologicalSpaceRealization, quotMk, quotMk_surjective, isQuotientMap_quotMk, continuous_quotMk, lift, lift_unique and hom_ext also occur in TDA.Reeb.CylinderPresentation (reeb-constructible-space.md), lift, lift_unique, hom_ext and ind in TDA.Reeb.ReebQuotient (reeb-quotient.md), and edgePoint and continuous_edgePoint in TDA.Reeb.RGraph (reeb-rgraph.md). A file opening more than one of these namespaces qualifies the overlapping names. Among the fixtures, fold, half, pointGraph, swapHom, swap_naturality and swap_ne_id also occur in other fixture namespaces.

Fixtures

TDA.Reeb.GraphRealizationExamples proves:

  • Empty vertex type. For every [IsEmpty V] in any universe, the realization, its path components and the graph components are empty, and both connectedness statements are false (empty_realization_isEmpty, empty_zerothHomotopy_isEmpty, empty_connectedComponent_isEmpty, empty_not_connected, empty_not_pathConnectedSpace).
  • One isolated vertex. The realization of ⊥ : SimpleGraph Unit is a point: it is Unique and homeomorphic to Unit (pointUnique, pointHomeomorph). Both component types have exactly one element (pointComponentsUnique, point_card_connectedComponent, point_card_zerothHomotopy), and the graph is connected with path-connected realization (point_connected, point_pathConnectedSpace).
  • One edge on two vertices. For ⊤ : SimpleGraph Bool and the dart d₀ : false → true, edgeHomeomorph : Realization ⊤ ≃ₜ unitInterval sends vertex false ↦ 0, vertex true ↦ 1, edgePoint d₀ t ↦ t and edgePoint d₀.symm t ↦ σ t, with inverse edgePoint d₀. The reversed dart at the reversed parameter is the same point (edge_reversed), and distinct parameters, interior ones included, give distinct points (edge_param_injective, edge_interior_ne).
  • Two disjoint edges. On Bool × Bool with edges (a, false) — (a, true), the path components are equivalent to Bool (twoEdgesComponents, twoEdges_card), the vertex classes c₀ and c₁ are distinct (c₀_ne_c₁), and every class is one of them (twoEdges_classification).
  • A two-edge path folded onto one edge. fold : pathGraph 3 →g ⊤ sends 0, 1, 2 to false, true, false. It identifies the nonadjacent ends 0 and 2 (fold_identifies_ends) and, pointwise off the shared vertex, the distinct edges 0 — 1 and 1 — 2 (fold_identifies_edges, separated by a set-level height). It is a graph homomorphism, not an edge contraction. The generator formulas hold on all three vertices and on the darts 0 → 1, 2 → 1 (image d₀) and 1 → 2 (image d₀.symm, with reversed edge coordinate fold_coord_d12). Naturality is evaluated at the interior point 1/2 of both orientations of the second edge (fold_naturality_d21, fold_naturality_d12).
  • A permutation of two components. swapHom exchanges the two disjoint edges. Its induced map on path components sends c₀ ↦ c₁ and c₁ ↦ c₀ and is not the identity (swap_c₀, swap_c₁, swap_ne_id). At c₀ both sides of the naturality square are the class of (true, false), which is not the class of c₀ (swap_naturality).
  • Infinite edgeless graphs. In an edgeless graph on any type, distinct vertices lie in distinct path components (bot_class_injective). On ℕ the vertex map and the class map are injective, there are infinitely many path components and the realization is not path connected (nat_vertex_injective, nat_class_injective, nat_zerothHomotopy_infinite, nat_not_pathConnectedSpace): no finiteness is assumed. On ℝ the realization is not path connected although ℝ is (real_class_injective, real_not_pathConnectedSpace): the topology of the vertex type is not used.

The fold lands in a connected graph, whose component type is a subsingleton, so its naturality square holds whatever the component maps are and does not discriminate at the level of components. Its discriminating content is in the generator and orientation formulas, which distinguish the two darts of the target edge. The component-level negative control is the swap: both of its classes are distinct, the induced map is not the identity, and the square at c₀ has a value different from c₀'s own class.

Source correspondence

Construction source. The cells, the relation, the quotient, the lift and its continuity, the edge and walk paths, the map of a graph homomorphism and the component label 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 copyright line is that of the source repository's LICENSE; the source file has no in-file notice, and the repository has no NOTICE file at that revision. The source is not imported and is not a dependency.

Adapted declarations, with source names and lines:

Library declaration Source declaration Lines
Cells, instTopologicalSpaceCells Cells and its topology 26–30
CellRel with symm, start RealisationRel 32–36
Realization, instTopologicalSpaceRealization Realisation and its topology 38–45
quotMk Realisation.mk 47–48
vertex, edgePoint vertex, edgePoint 50–54
edgePoint_symm, edgePoint_zero, edgePoint_one the same, private 56–70
isQuotientMap_quotMk isQuotientMap_mk, private 72–73
ind realisation_induction, private 75–82
lift lift 84–92
lift_vertex, lift_edgePoint, continuous_lift the same, private 94–111
continuous_edgePoint the same, private 155–158
edgePath, walkPath edgePath, walkPath 160–171
realizationMap map 173–188
realizationMap_vertex, realizationMap_edgePoint map_vertex, map_edgePoint, private 190–195
componentLabel, componentLabel_eq_of_joined the label f and its continuity into the discrete component type in connected_of_pathConnectedSpace, private 202–219

Changes: the names; public visibility of every adapted private lemma and of the component label; vertex and edgePoint defined through quotMk; ind through surjectivity of quotMk; realizationMap built from continuousLift, with independent vertex universes, where the source's map requires both vertex types in one universe; and constancy of the label along paths through TDA.Reeb.joined_eq_of_discrete, where the source uses constancy on a preconnected space.

New declarations: isOpen_vertexCell, quotMk_surjective, continuous_quotMk, quotMk_eq_quotMk_iff, function_ext, hom_ext, lift_unique, continuousLift, continuousLift_vertex, continuousLift_edgePoint, continuousLift_unique, existsUnique_continuousLift, vertex_injective, instIsEmptyRealization, instNonemptyRealization, edgePath_apply, edgeSegment, edgeSegment_apply, edgeSegment_zero, edgeSegment_one, walkPath_nil, walkPath_cons, joined_vertex_of_reachable, the private straight path pathToZero, joined_edgePoint_vertex, realizationMap_id, realizationMap_comp, componentLabel_vertex, componentLabel_edgePoint, joined_vertex_iff, mk_edgePoint, componentsEquiv with its three formulas, componentsEquiv_componentMap, componentsEquiv_comp_componentMap, componentMap_componentsEquiv_symm, componentMap_realizationMap_id, componentMap_realizationMap_comp, connected_iff_pathConnectedSpace, and every fixture. The source has the direction from a path-connected realization to a connected graph only as a private lemma, and no bundled lift, lift uniqueness, vertex injectivity, component equivalence, naturality, or identity and composition laws for its map.

de Silva, Munch and Patel. Categorified Reeb Graphs, Notation 2.7, describes a finite ℝ-graph as the quotient of the disjoint union of vertex points Vᵢ × {aᵢ} and edge intervals Eᵢ × [aᵢ, aᵢ₊₁] by the endpoint identifications. This is context for the cell construction: there the vertex and edge sets are finite, edges are oriented by height and there is no reversal relation. The realization of arbitrary simple graphs, its path-component equivalence and its naturality are library constructions, not results of the paper. The library's realization of height-indexed presentations, TDA.Reeb.CylinderPresentation.Realization, is a different construction (reeb-constructible-space.md).

Mathlib and TauCeti. Pinned mathlib has the affine simplicial complex of a simple graph, Geometry.SimplicialComplex.ofSimpleGraph in V →₀ 𝕜 (Mathlib/Analysis/Convex/SimplicialComplex/AffineIndependentUnion.lean, for [DecidableEq V], [DecidableEq 𝕜] and a linearly ordered field 𝕜), with the vertices as 0-simplices at basis vectors and the edges as 1-simplices; it has no quotient description, lift, induced maps or path-component API. No file under Topology or AlgebraicTopology uses SimpleGraph. The realization SSet.toTop is that of simplicial sets. TopCat.zerothHomotopyEquiv is not a realization construction: it compares ZerothHomotopy X with the connected components π₀ of the singular simplicial set of X. TauCeti, at revision 3b4a078d372e27f93b0c181e6b67df93797d1a02, has a realization of abstract simplicial complexes under TauCeti/AlgebraicTopology/SimplicialComplex/Realization/. Its SimpleGraph files lie under TauCeti/Combinatorics/SimpleGraph/ and in TauCeti/LinearAlgebra/RootSystem/FiniteType/SimpleGraph.lean, and no path under TauCeti/Topology/ or TauCeti/AlgebraicTopology/ names SimpleGraph. This is a partial check, not a content-level inspection of every file, so it does not establish that TauCeti has no simple-graph realization. Nothing from TauCeti is used, and TauCeti is not a dependency.

Not claimed here: edge contraction; the fundamental group of a triangle or any other higher homotopy; trees as simply connected realizations, which are in reeb-graph-cycle-obstruction.md and reeb-graph-tree-contraction.md; realization of Hasse orders; piecewise-linear heights and cell graphs of interval preimages, which are in reeb-graph-pl.md; comparisons with multigraphs, cylinder presentations or simplicial sets; a product-of-quotient-maps lemma; a continuous retraction of the realization to its vertices.

Sources: de Silva, Munch and Patel, Categorified Reeb Graphs, §2.3, Notation 2.7; pinned mathlib graph components, graph homomorphisms on darts and path components; subpaths supply the parameterized dart paths.