Lower Bounding the Gromov-Hausdorff Distance in Metric Graphs

Adams, Henry; Majhi, Sushovan; Manin, Fedor; Virk, Žiga; Zava, Nicolò

doi:10.4230/LIPIcs.SoCG.2026.3

Lower Bounding the Gromov–Hausdorff Distance in Metric Graphs

Henry Adams

University of Florida, Gainesville, FL, USA Sushovan Majhi

George Washington University, Washington, DC, USA Fedor Manin

University of Toronto, Canada Žiga Virk

University of Ljubljana, Slovenia
Institute IMFM, Ljubljana, Slovenia Nicolò Zava

Institute of Science and Technology, Klosterneuburg, Austria

Abstract

Let $G$ be a finite, connected metric graph and let $X$ be a subset of $G$ . If $X$ is sufficiently dense in $G$ , we show that the Gromov–Hausdorff distance matches the Hausdorff distance, namely $d_{\mathrm{GH}}(G,X)=d_{\mathrm{H}}(G,X)$ . When the metric graph is the circle $G=S^{1}$ with circumference $2\pi$ , a recent study established the equality $d_{\mathrm{GH}}(S^{1},X)=d_{\mathrm{H}}(S^{1},X)$ whenever $d_{\mathrm{GH}}(S^{1},X)<\frac{\pi}{6}$ . Our results relax this hypothesis to $d_{\mathrm{GH}}(S^{1},X)<\frac{\pi}{3}$ , and furthermore, we show that the constant $\frac{\pi}{3}$ is the best possible. We lower bound the Gromov–Hausdorff distance $d_{\mathrm{GH}}(G,X)$ by the Hausdorff distance $d_{\mathrm{H}}(G,X)$ via a simple topological obstruction: the existence of a possibly discontinuous function $f\colon G\to X$ with too small distortion contradicts the connectedness of $G$ .

Keywords and phrases:

Gromov–Hausdorff distance, distortion, connectedness, Borsuk–Ulam theorem

Funding:

Henry Adams: Simons Foundation Travel Support for Mathematicians.

Žiga Virk: Slovene research agency grant P1-0292.

Nicolò Zava: FWF Grant, Project number I4245-N35.

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Topology ; Mathematics of computing

\rightarrow

Graph theory

Editors:

Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The Gromov–Hausdorff distance between two abstract metric spaces $(X,d_{X})$ and $(Y,d_{Y})$ , denoted $d_{\mathrm{GH}}(X,Y)$ , provides a dissimilarity measure quantifying how far the two metric spaces are from being isometric [13, 14, 24]. In the past two decades, this distance has found applications in topological data analysis (TDA) as a theoretical framework for shape and dataset comparison [21], which motivated the study of its quantitative aspects. However, precise computations of the Gromov–Hausdorff distance between even simple spaces are mostly unknown, with certain exceptions such as the Gromov–Hausdorff distance between a line segment and a circle [16] and between spheres of certain dimensions [19, 1, 15]. Even approximating the Gromov–Hausdorff distance by a factor of $3$ in the case of trees with unit-edge length is known to be NP-hard [4, 23]. A better approximation factor can only be achieved in very special cases; for example, [20] provides a $\frac{5}{4}$ -approximation scheme if $X$ and $Y$ are finite subsets of the real line. Developing tools and pipelines to estimate the Gromov–Hausdorff distance is a central research direction in the applied topology community. To estimate the Gromov–Hausdorff distance between two metric spaces $X, Y$ , one may:
(A) Find nice samples $X^{\prime}\subseteq X$ and $Y^{\prime}\subseteq Y$ approximating the geometry of $X$ and $Y$ , and
(B) Efficiently bound the Gromov–Hausdorff distance between the subsets $X^{\prime}$ and $Y^{\prime}$ .
Indeed, when $X$ and $Y$ are infinite continuous objects – e.g., Riemannian manifolds, metric graphs – and one wants to use computational machinery, it is often essential to resort to finite subsets approximating the geometry of the original spaces.

We reformulate the first task (A) as follows: how dense does the sample $X^{\prime}$ have to be in $X$ to capture the geometry of the ambient space $X$ ? To systematize this question, we use the Hausdorff distance as a measure of density and ask if we can provide a threshold $\varepsilon$ and constant $0<C\leq 1$ such that $d_{\mathrm{GH}}(X,X^{\prime})\geq C\cdot d_{\mathrm{H}}(X,X^{\prime})$ whenever $d_{\mathrm{H}}(X,X^{\prime})<\varepsilon$ . In particular, $d_{\mathrm{GH}}(X,X^{\prime})=d_{\mathrm{H}}(X,X^{\prime})$ if $C=1$ . In [2], the authors show that when $X$ is a manifold and $d_{\mathrm{GH}}(X,X^{\prime})<\varepsilon$ (which is implied by $d_{\mathrm{H}}(X,X^{\prime})<\varepsilon$ ) for some constant $\varepsilon$ , then $d_{\mathrm{GH}}(X^{\prime},X)\geq C\cdot d_{\mathrm{H}}(X,X^{\prime})$ for some $\frac{1}{2}\leq C\leq 1$ . Our study continues that investigation and proves improved results when $X$ is a metric graph, hence relaxing the manifold assumption.

A fruitful approach to provide bounds on the Gromov–Hausdorff distance in task (B) is to use stable metric invariants. One associates each metric space $X$ with a value $\psi(X)$ in a simpler metric space so that $\psi(X)$ and $\psi(Y)$ are close whenever $X$ and $Y$ are. An immediate example is the diameter; we have $d_{\mathrm{GH}}(X,Y)\geq\frac{1}{2}|\mathrm{diam}(X)-\mathrm{diam}(Y)|$ . For further stable metric invariants, we refer the reader to curvature sets [22], to Vietoris–Rips persistence diagrams [11], and to hierarchical clustering [10]. In [25], dimension theory is used to limit the precision of metric invariants with values in Hilbert spaces.

One of the precursors of algebraic topology was Brouwer’s proof of invariance of dimension, namely that $\mathbb{R}^{m}$ is not homeomorphic to $\mathbb{R}^{n}$ for $n>m$ . Proving $\mathbb{R}^{1}$ is not homeomorphic to $\mathbb{R}^{n}$ for $n>1$ relies only on connectedness: removing a single point from $\mathbb{R}^{1}$ leaves a disconnected space. To prove invariance of dimension for $n>m\geq 2$ , Brouwer relied on concepts related to the degree of a map between spheres [8, 7], which is often now formalized using higher-dimensional homology groups. The topological obstructions to small Gromov–Hausdorff distances in [2] relied on homological tools, namely the fundamental class of a manifold. One of the key contributions of our paper is to go “back in time” and produce strong lower bounds on Gromov–Hausdorff distances using simpler topological tools: we show that small Gromov–Hausdorff distances would contradict the connectedness of a space.

Overview of our results

Let $G$ be a connected, finite metric graph, and let $X\subseteq G$ be a subset. We show how to lower bound the Gromov–Hausdorff distance $d_{\mathrm{GH}}(G,X)$ in terms of the Hausdorff distance $d_{\mathrm{H}}(G,X)$ , achieving $d_{\mathrm{GH}}(G,X)=d_{\mathrm{H}}(G,X)$ . A unifying theme in our proofs is that we show that a possibly discontinuous function $f\colon G\to X$ induces a continuous and non-surjective map $\overline{f}\colon G\to G$ . We then use non-surjectivity (and related properties) to lower bound the distortion of $\overline{f}$ and $f$ , hence lower bounding $d_{\mathrm{GH}}(G,X)$ . The simplest metric graph is a tree $T$ . Let $\partial T$ denote the leaves of $T$ , and let $\vec{d}_{\mathrm{H}}(\partial T,X)$ denote the directed Hausdorff distance from $\partial T$ to the sample $X$ (see Section 2). We show:

Theorem 8.

Let $T$ be a finite metric tree and let $X\subseteq T$ . If $d_{\mathrm{H}}(T,X)>\vec{d}_{\mathrm{H}}(\partial T,X)$ , then $d_{\mathrm{GH}}(T,X)=d_{\mathrm{H}}(T,X)$ . The interpretation is as follows: if the biggest gaps in the sampling $X\subseteq T$ are not near the leaves of $T$ (which by Proposition 6 is typical behavior), then $d_{\mathrm{GH}}(T,X)=d_{\mathrm{H}}(T,X)$ . Some control on the leaf vertices is needed:

Theorem 5.

For any $\varepsilon>0$ there exists a finite metric tree $T$ and a closed subset $X\subseteq T$ such that $d_{\mathrm{GH}}(T,X)\leq\varepsilon\cdot d_{\mathrm{H}}(T,X)$ .

When $G=S^{1}$ is the circle of circumference $2\pi$ , [2] shows that if $d_{\mathrm{GH}}(S^{1},X)<\frac{\pi}{6}$ , then $d_{\mathrm{GH}}(S^{1},X)=d_{\mathrm{H}}(S^{1},X)$ . The following theorem improves the constant $\frac{\pi}{6}$ to $\frac{\pi}{3}$ .

Theorem 11.

For any subset $X\subseteq S^{1}$ , we have $d_{\mathrm{GH}}(S^{1},X)\geq\min\left\{d_{\mathrm{H}}(S^{1},X),\ \tfrac{\pi}{3% }\right\}$ .

In Theorem 12 we show that this constant $\frac{\pi}{3}$ is the best possible, namely that for any $\varepsilon\in\left(0,\frac{\pi}{6}\right)$ , there exists a nonempty compact subset $X\subseteq S^{1}$ with $d_{\mathrm{H}}(S^{1},X)=\frac{\pi}{3}+\varepsilon$ and $d_{\mathrm{GH}}(S^{1},X)=\frac{\pi}{3}<d_{\mathrm{H}}(S^{1},X)$ . We generalize the above results for the circle and trees to general metric graphs. Let $G$ be a finite metric graph with set of leaf vertices $\partial G$ . We prove that if $X$ is dense enough relative to $e(G_{0})$ , which is the smallest edge length between vertices in the core $G_{0}$ of $G$ (see Section 2), then the Gromov–Hausdorff distance matches the Hausdorff distance.

Theorem 23.

Let $G$ be a finite connected metric graph and let $X\subseteq G$ . If $\partial G\neq\emptyset$ , suppose $d_{\mathrm{H}}(G,X)>\vec{d}_{\mathrm{H}}(\partial G,X)$ . If $d_{\mathrm{GH}}(G,X)<\tfrac{e(G_{0})}{16}$ , then $d_{\mathrm{GH}}(G,X)=d_{\mathrm{H}}(G,X)$ . Theorems 11 and 23 are obtained using low-dimensional versions of the Borsuk–Ulam theorem for maps from the circle into $\mathbb{R}$ or into a tree, which are proven using connectedness. Our results have corollaries allowing us to lower bound the Gromov–Hausdorff distance between two subsets $X,Y\subseteq G$ , using the triangle inequality. That is, for two sufficiently dense subsets $X,Y\subseteq G$ , we provide new lower bounds on $d_{\mathrm{GH}}(X,Y)$ in terms of the Hausdorff distance $d_{\mathrm{H}}(X,Y)$ , which is $\mathcal{O}(n^{2})$ -time computable if the subsets have at most $n$ points. We demonstrate such a corollary explicitly in the case of metric trees in Section 4.

Organization of the paper

We begin in Section 2 with background. In Section 3, we show that some control over the boundary of the metric graph is necessary. We begin with metric trees in Section 4, proceed to the circle in Section 5, and consider general metric graphs in Section 6.

2 Background and notation

We refer the reader to [9, 6] for more information on metric spaces, metric graphs, the Hausdorff distance, and the Gromov–Hausdorff distance.

2.1 Metric spaces

Let $(Z,d)$ be a metric space. For $z\in Z$ , we let $B(z;r)=\{z^{\prime}\in Z\nobreak\ |\nobreak\ d(z,z^{\prime})<r\}$ denote the open metric ball of radius $r$ about $z$ . For any $r\geq 0$ and $A\subseteq Z$ , we denote the $r$ -thickening of $A$ in $Z$ , namely, the union of metric balls of radius $r$ centered at the points of $A$ , by

A^{r}=\cup_{a\in A}B(a;r)=\left\{z\in Z\mid\inf_{a\in A}d(a,z)<r\right\}.

The diameter of a subset $A\subseteq Z$ is the supremum of all distances between pairs of points of $A$ . More formally, the diameter is defined as $\mathrm{diam}(A)=\sup\{d(a,a^{\prime})\mid a,a^{\prime}\in A\}$ .

2.2 Metric graphs

To define metric graphs, we follow Definitions 3.1.12 (quotient metric) and 3.2.9 (metric graph) of [9]. A metric segment is a metric space isometric to a real line segment $[0,l]$ for $l\geq 0$ . Our metric graphs will be connected and have a finite number of vertices and edges.

Definition 1 (Metric Graph).

A finite metric graph $(G,d)$ is the metric space obtained by gluing a finite collection $E$ of metric segments along their boundaries to a finite collection $V$ of vertices, and equipping the result $\left(\bigsqcup_{e\in E}e\right)/\sim$ with the quotient metric. We assume this equivalence relation results in a connected space.

The metric segments $e\in E$ are the edges and the equivalence classes of their endpoints in $V$ are the vertices of $G$ . Since $G$ is connected, we have $d(y,y^{\prime})<\infty$ for all $y,y^{\prime}\in G$ . Since $E$ is finite, the quotient semi-metric [9, Definition 3.1.12] is in fact a metric.¹¹1One needs to be careful if $E$ is infinite. Suppose one has two vertices $v$ and $v^{\prime}$ , and one edge $e_{n}$ of length $\frac{1}{n}$ with endpoints $v$ and $v^{\prime}$ for each $n\in\mathbb{N}$ . The quotient semi-metric gives $d(v,v^{\prime})=\inf_{n\in\mathbb{N}}\frac{1}{n}=0$ though $v\neq v^{\prime}$ ; this semi-metric is not a metric. These subtleties disappear since we assume $E$ is finite. For an edge $e\in E$ , its length $|e|$ is the length of the corresponding metric segment. Note that the length can be different from the distance between the endpoints of $e$ according to the metric $d$ . Extending the definition of length for a continuous path $\gamma\colon[a,b]\to G$ , we define the length $|\gamma|$ as the sum of the (full or partial) lengths of the edges that $\gamma$ traverses. For a vertex $v$ of a graph, its degree, denoted $deg(v)$ , is the number of edges incident to $v$ . A self-loop at $v$ contributes $2$ to the degree of $v$ . As an example, the circle $S^{1}$ can be given a metric graph structure with a single vertex $v$ of degree $2$ at the north pole, along with a self-loop. We denote the set of leaf vertices, i.e. the vertices of degree one, by $\partial G$ . A metric graph $G$ is therefore endowed with two layers of information: a metric structure turning it into a length space [9, Definition 2.1.6] and a combinatorial structure $(V,E)$ as an abstract graph. Using the above definition, we are also allowing $G$ to have single-edge cycles and multiple edges between a pair of vertices. In this paper, we only consider path connected metric graphs $(G,d)$ with finitely many edges. Therefore, the metric graphs we consider are compact, and since a compact length space is geodesic, they are also geodesic (meaning for every $x,y\in G$ there is an isometric embedding $\gamma\colon[0,d(x,y)]\to G$ such that $\gamma(0)=x$ and $\gamma(d(x,y))=y$ ). This justifies why for any $y,y^{\prime}\in G$ , there is always at least one shortest path or geodesic path $\gamma$ in $G$ joining $y,y^{\prime}$ whose length satisfies $|\gamma|=d(y,y^{\prime})$ . We define an undirected simple loop $\mathcal{\gamma}$ of $G$ to be a simple path that intersects itself only at the endpoints. We denote by $\mathcal{L}(G)$ the finite set of all simple loops of the finite graph $G$ . Since a metric tree is a metric graph with no loops, $\mathcal{L}(G)=\emptyset$ for a metric tree $G$ . For a metric graph $G$ , let $e(G)$ denote the length of the shortest edge in $G$ . If for $A\subseteq G$ there exists a unique shortest geodesic in $G$ between any points $a,a^{\prime}\in A$ , then we define the (geodesic) convex hull of $A$ in $G$ to be the union of geodesics between all $a$ and $a^{\prime}$ . If $\mathrm{diam}(A)<\frac{e(G)}{2}$ , then the convex hull of $A$ is well-defined. Given a (connected and finite) metric graph $G$ , let $G_{0}$ be the smallest connected subgraph of $G$ containing the union of all simple loops of $G$ . We call $G_{0}$ the core of $G$ . If $G$ has no leaf edges, then $G=G_{0}$ . Note that $G_{0}$ is just $G$ with its “hanging trees” removed, or in other words, the minimal subspace onto which $G$ deformation retracts. We will use the following two properties about $G_{0}$ . First, if $G$ (and hence $G_{0}$ ) contains at least two simple loops, then at least one vertex of $G_{0}$ has degree at least $3$ . We can then consider the canonical graph representation of $G_{0}$ consisting of only vertices of degree at least $3$ . Second, we note that if a path connected subset $Z\subseteq G$ has first Betti number equal to the first Betti number of $G$ , then $G_{0}\subseteq Z$ .

2.3 Hausdorff distances

Let $(Z,d)$ be a metric space. If $X$ and $Y$ are two subsets of $Z$ , then the directed Hausdorff distance from $X$ to $Y$ , denoted $\vec{d}_{\mathrm{H}}(X,Y)$ , is defined by

\vec{d}_{\mathrm{H}}(X,Y)=\sup_{x\in X}\inf_{y\in Y}d(x,y)=\inf\bigg\{r\geq 0% \mid X\subseteq Y^{r}\bigg\}.

Note that $\vec{d}_{\mathrm{H}}(X,Y)$ is not symmetric in general. To retain symmetry, the Hausdorff distance, denoted $d_{\mathrm{H}}(X,Y)$ , is defined as $d_{\mathrm{H}}(X,Y)=\max\left\{\vec{d}_{\mathrm{H}}(X,Y),\vec{d}_{\mathrm{H}}(% Y,X)\right\}.$ In other words, the Hausdorff distance finds the infimum over all real numbers $r$ such that if we thicken $Y$ by $r$ it contains $X$ , and if we thicken $X$ by $r$ it contains $Y$ . If no such $r$ exists then the Hausdorff distance is infinity.

2.4 Gromov–Hausdorff distances

Let $(X,d_{X})$ and $(Y,d_{Y})$ be metric spaces. In equations (1)–(3) we give three equivalent definitions of the Gromov–Hausdorff distance between $X$ and $Y$ . The first definition follows [14]. The Gromov–Hausdorff distance $d_{\mathrm{GH}}(X,Y)$ is the infimum of the Hausdorff distances between $F(X)$ and $G(Y)$ in $Z$ , with the infimum being over all metric spaces $Z$ and all isometric embeddings $F\colon X\hookrightarrow Z$ and $G\colon Y\hookrightarrow Z$ :

d_{\mathrm{GH}}(X,Y)=\inf_{F,G,Z}d_{\mathrm{H}}(F(X),G(Y)).

(1)

The second definition uses correspondences. A relation $\mathcal{R}\subseteq X\times Y$ is a correspondence if for every $x\in X$ there is some $y\in Y$ with $(x,y)\in\mathcal{R}$ , and for every $y\in Y$ there is some $x\in X$ exists with $(x,y)\in\mathcal{R}$ . The distortion of a correspondence $\mathcal{R}$ is

\mathrm{dis}(\mathcal{R})=\sup_{(x,y),(x^{\prime},y^{\prime})\in\mathcal{R}}% \left|d_{X}(x,x^{\prime})-d_{Y}(y,y^{\prime})\right|.

The Gromov–Hausdorff distance between two (arbitrary) metric spaces $X$ and $Y$ is

d_{\mathrm{GH}}(X,Y)=\tfrac{1}{2}\inf_{\mathcal{R}\subseteq X\times Y}\mathrm{% dis}(\mathcal{R}),

(2)

where the infimum is taken over all correspondences $\mathcal{R}$ between $X$ and $Y$ [9, 17]. For metric spaces $(X,d_{X})$ and $(Y,d_{Y})$ , let $f\colon X\to Y$ and $g\colon Y\to X$ be two (possibly discontinuous) functions between them. We define the distortion of $f$ as

\mathrm{dis}(f)=\sup_{x,x^{\prime}\in X}\left|d_{X}(x,x^{\prime})-d_{Y}(f(x),f% (x^{\prime}))\right|.

The distortion of $g$ is defined similarly. The codistortion of $f$ and $g$ is defined as

\mathrm{codis}(f,g)=\sup_{x\in X,y\in Y}\left|d_{X}(x,g(y))-d_{Y}(f(x),y)% \right|.

Kalton and Ostrovskii [17] show that

d_{\mathrm{GH}}(X,Y)=\tfrac{1}{2}\inf_{f,g}\max\{\mathrm{dis}(f),\mathrm{dis}(% g),\mathrm{codis}(f,g)\},

(3)

where $f\colon X\to Y$ and $g\colon Y\to X$ are any functions. It follows that if $d_{\mathrm{GH}}(X,Y)<C$ , then there is some function $f\colon X\to Y$ with $\frac{1}{2}\mathrm{dis}(f)<C$ .

2.5 Gromov–Hausdorff distances and compactness

The following result is folklore; see [3] for the proof.

Lemma 2.

Let $X$ be a metric space and $Y$ be a subset thereof. Let us denote by $\overline{Y}$ the closure of $Y$ in $X$ . Then

d_{\mathrm{H}}(X,Y)=d_{\mathrm{H}}(X,\overline{Y})\quad\text{and}\quad d_{% \mathrm{GH}}(X,Y)=d_{\mathrm{GH}}(X,\overline{Y}).

Furthermore, for every two subsets $Y$ and $Z$ of $X$ , we have $\vec{d}_{\mathrm{H}}(Z,Y)=\vec{d}_{\mathrm{H}}(Z,\overline{Y})$ .

We will consistently apply Lemma 2 when the ambient metric space is compact. Thus, when we are studying the Hausdorff and the Gromov–Hausdorff distances between a compact metric space and a subspace thereof, we can assume that the subspace is compact as well.

2.6 Gromov–Hausdorff distances and connectedness

Lemma 3.

Let $f\colon X\to Y$ be a function between metric spaces, with $X$ path-connected and $Y$ geodesic. Then for every $r>\tfrac{\mathrm{dis}(f)}{2}$ , the thickening $f(X)^{r}$ is path connected.

Proof.

Let $y_{1},y_{2}\in f(X)^{r}$ and $x_{1},x_{2}\in X$ be points such that $d_{Y}(y_{i},f(x_{i}))<r$ for $i=1,2$ . Since $Y$ is geodesic, the entire geodesic connecting $y_{i}$ to $f(x_{i})$ is contained in $B(f(x_{i}),r)\subseteq f(X)^{r}$ . Pick $\varepsilon>0$ sufficiently small to satisfy $r>\tfrac{\mathrm{dis}(f)}{2}+\varepsilon$ . Since $X$ is path connected, there are $z_{1}=x_{1},z_{2},\dots,z_{n+1}=x_{2}$ such that $d(z_{j},z_{j+1})<\varepsilon$ for every $j=0,\dots,n$ . Thus, $d(f(z_{j}),f(z_{j+1}))<\mathrm{dis}(f)+\varepsilon$ . Since $Y$ is geodesic, there are $m_{j}\in Y$ such that $d(f(z_{j}),m_{j})=d(f(z_{j+1}),m_{j})=\tfrac{1}{2}d(f(z_{j}),f(z_{j+1}))<r$ and the geodesics connecting $m_{j}$ to $f(z_{j})$ and $f(z_{j+1})$ are contained in $f(X)^{r}$ . $\hfill\blacktriangleleft$

2.7 Gromov–Hausdorff distances and graphs

Let $G$ be a finite metric graph and let $X\subseteq G$ be a compact subset. To use functions $f\colon G\to X$ to prove bounds on the Gromov–Hausdorff distance, we need to be a bit careful. Indeed, even if the sample $X$ is close to the leaves of $G$ , it may be that $f(G)$ is not close to the leaves. Luckily, we have a lot of freedom to construct our function $f$ :

Lemma 4.

Let $G$ be a finite metric graph and let $X\subseteq G$ be compact. If $d_{\mathrm{GH}}(G,X)<r$ , then there is a function $f\colon G\to X$ with $\frac{1}{2}\mathrm{dis}(f)<r$ and $\vec{d}_{\mathrm{H}}(\partial G,f(G))=\vec{d}_{\mathrm{H}}(\partial G,X)$ .

Proof.

Let $\mathcal{R}\subseteq G\times X$ be a correspondence satisfying $\mathrm{dis}(\mathcal{R})<2r$ . Fix $\varepsilon>0$ such that $\mathrm{dis}(\mathcal{R})+\varepsilon<2r$ . For every $v\in\partial G$ , pick $x_{v}\in X$ as a point satisfying $d(v,x_{v})=\min_{x\in X}d(v,x)$ . We first recursively construct a surjective map $\widetilde{f}$ from a subset of $G$ to $\{x_{v}\mid v\in\partial G\}$ . Let us arbitrarily order the leaves $v_{1},\dots,v_{n}$ and denote the point $x_{v_{i}}$ by $x_{i}$ for the sake of simplicity. Base step. Pick any $y_{1}\in G$ such that $(y_{1},x_{1})\in\mathcal{R}$ and set $\widetilde{f}(y_{1})=x_{1}$ . Recursive step. Assume we have defined $y_{1},\dots,y_{m}\in G$ distinct and set $\widetilde{f}(y_{i})=x_{i}$ . Pick $y\in G$ satisfying $(y,x_{m+1})\in\mathcal{R}$ . Let us distinguish two cases. If $y\notin\{y_{1},\dots,y_{m}\}$ , then set $y_{m+1}=y$ and $\widetilde{f}(y_{m+1})=x_{m+1}$ . Otherwise, fix an arbitrary point $y_{m+1}\in G\setminus\{y_{1},\dots,y_{m}\}$ satisfying $d(y_{m+1},y)<\frac{\varepsilon}{2}$ and define $\widetilde{f}(y_{m+1})=x_{m+1}$ . Consider an arbitrary extension $f\colon G\to X$ of $\widetilde{f}\colon\{y_{1},\dots,y_{n}\}\to\{x_{1},\dots,x_{n}\}$ with the property that the graph of $f|_{G\setminus\{y_{1},\dots,y_{n}\}}$ is contained in $\mathcal{R}$ . Then $\mathrm{dis}(f)\leq\mathrm{dis}(\mathcal{R})+2\cdot\tfrac{\varepsilon}{2}<2r$ and $\vec{d}_{\mathrm{H}}(\partial G,f(G))=\vec{d}_{\mathrm{H}}(\partial G,X)$ by construction. $\hfill\blacktriangleleft$ It is worth noticing that in the proof above we did not use any property of $\partial G$ , and the result can be shown with $\partial G$ replaced by any finite subset $Y$ of $G$ .

3 Ratio of $d_{\mathrm{GH}}$ vs $d_{\mathrm{H}}$ can be arbitrarily small for metric trees

In this section we prove Theorem 5, a variant of Theorem 5 of [2], now adapted to metric trees. As we show in Theorems 8 and 23, the Gromov–Hausdorff distance $d_{\mathrm{GH}}(T,X)$ between a metric graph $T$ and a subset $X\subseteq T$ can be bounded below by their Hausdorff distance $d_{\mathrm{H}}(T,X)$ when $X$ is close enough to the leaves of $T$ , i.e., when $d_{\mathrm{H}}(T,X)>\vec{d}_{\mathrm{H}}(\partial T,X)$ . When $d_{\mathrm{H}}(T,X)<\vec{d}_{\mathrm{H}}(\partial T,X)$ , however, the ratio of $d_{\mathrm{GH}}(T,X)$ over $d_{\mathrm{H}}(T,X)$ can become arbitrarily small as we show below. Furthermore, Theorem 5 suggests that $\partial T$ may not map close to itself via correspondences with small distortion; see Figure 1.

Figure 1: A sketch of the construction of Theorem 5: (left) The metric tree

T

, (middle) the bold superimposed

X^{\prime}\subseteq T

with small

d_{\mathrm{H}}(T,X^{\prime})

, and (right) a different isometric embedding of

X^{\prime}

into

T

indicated by

X\subseteq T

with large

d_{\mathrm{H}}(T,X)

.

Theorem 5.

For any $\varepsilon>0$ there exists a finite metric tree $T$ and a closed subset $X\subseteq T$ such that $d_{\mathrm{GH}}(T,X)\leq\varepsilon\cdot d_{\mathrm{H}}(T,X)$ .

Proof.

Choose $n\in\mathbb{N}$ and let $\varepsilon=\frac{1}{n}$ . For $t\geq 0$ , let $I(t)$ be a copy of the interval $[0,t]$ with a designated basepoint $0$ . Define a metric tree $T$ as the wedge of $n$ intervals of lengths $1+\varepsilon,1+2\varepsilon,\ldots,1+n\varepsilon=2$ , and define a metric tree $X_{0}$ as the wedge of intervals of lengths $1,1+\varepsilon,1+2\varepsilon,\ldots,1+(n-1)\varepsilon=2-\varepsilon$ :

T=\bigvee_{t=1}^{n}I(1+t\cdot\varepsilon)\quad\text{ and }\quad X_{0}=\bigvee_% {t=0}^{n-1}I(1+t\cdot\varepsilon).

Recall from (1) that $d_{\mathrm{GH}}(T,X)$ is the infimum of the Hausdorff distances between $F(T)$ and $G(X)$ in $Z$ , with the infimum being over all metric spaces $Z$ and all isometric embeddings $F\colon T\hookrightarrow Z$ and $G\colon X\hookrightarrow Z$ . In Figure 1 we have two different isometric embeddings $X^{\prime},X$ of the same tree $X_{0}$ into $Z=T$ : one with a small Hausdorff distance $d_{\mathrm{H}}(T,X^{\prime})=\varepsilon$ as $X^{\prime}$ is $T$ with each ray being shortened by $\varepsilon$ , and one with a large Hausdorff distance $d_{\mathrm{H}}(T,X)=1$ as $X$ is $T$ with the longest ray $I(2)$ of length $2$ being replaced with a subray $I(1)$ of length $1$ . By (1), we have $d_{\mathrm{GH}}(T,X)\leq d_{\mathrm{H}}(T,X^{\prime})=\varepsilon d_{\mathrm{H% }}(T,X)$ . $\hfill\blacktriangleleft$

4 Metric trees with coefficient $1$

Section 3 demonstrates that results claiming $d_{\mathrm{GH}}(G,X)=d_{\mathrm{H}}(G,X)$ for $X$ a subset of a metric graph $G$ do not hold in general, even if $d_{\mathrm{H}}(G,X)$ is arbitrarily small. In this section, as well as in Section 6, we prove related results relying on bounds on $\vec{d}_{\mathrm{H}}(\partial G,X)$ . In particular, we will assume the condition $d_{\mathrm{H}}(G,X)>\vec{d}_{\mathrm{H}}(\partial G,X)$ which rules out the example constructed in Theorem 5. The following proposition shows that condition has a high probability of being satisfied if $X$ is a large uniform sample of $G$ ; see [3] for the proof.

Proposition 6.

If $G$ is a metric graph and $X$ is a sample of $n$ uniformly random points, then with high probability as $n\to\infty$ , we have $d_{\mathrm{H}}(G,X)>\vec{d}_{\mathrm{H}}(\partial G,X)$ .

We prove the following results for metric trees.

Proposition 7.

Let $T$ be a finite tree, and let $f\colon T\to T$ be a function. If $d_{\mathrm{H}}(T,f(T))>\vec{d}_{\mathrm{H}}(\partial T,f(T))$ , then $\tfrac{1}{2}\mathrm{dis}(f)\geq d_{\mathrm{H}}(T,f(T))$ .

Proof.

Let $\tfrac{1}{2}\mathrm{dis}(f)<r$ and let $\overline{x}\in T$ be a point such that $B(\overline{x},d_{\mathrm{H}}(T,f(T)))\cap f(T)=\emptyset$ . The assumption $d_{\mathrm{H}}(T,f(T))>\vec{d}_{\mathrm{H}}(\partial T,f(T))$ implies that $T\setminus\{\overline{x}\}$ is disconnected and at least two distinct components thereof have non-empty intersection with $f(T)$ (since a tree has at least two leaves). Since $f(T)^{r}$ is connected by Lemma 3, we have $\overline{x}\in f(T)^{r}$ , which implies $d_{\mathrm{H}}(T,f(T))<r$ . Since $r$ can be taken arbitrarily, $d_{\mathrm{H}}(T,f(T))\leq\tfrac{1}{2}\mathrm{dis}(f)$ . $\hfill\blacktriangleleft$

Theorem 8.

Let $T$ be a finite metric tree and let $X\subseteq T$ . If $d_{\mathrm{H}}(T,X)>\vec{d}_{\mathrm{H}}(\partial T,X)$ , then $d_{\mathrm{GH}}(T,X)=d_{\mathrm{H}}(T,X)$ .

Proof.

By Lemma 2, we may assume that $X$ is compact. Suppose for a contradiction that $d_{\mathrm{GH}}(T,X)<d_{\mathrm{H}}(T,X)$ . Then by Lemma 4, there is a function $f\colon T\to X\subseteq T$ with $\tfrac{1}{2}\mathrm{dis}(f)<d_{\mathrm{H}}(T,X)\leq d_{\mathrm{H}}(T,f(T))$ and $\vec{d}_{\mathrm{H}}(\partial T,f(T))=\vec{d}_{\mathrm{H}}(\partial T,X)<d_{% \mathrm{H}}(T,X)\leq d_{\mathrm{H}}(T,f(T))$ , contradicting Proposition 7. $\hfill\blacktriangleleft$ In other words, $d_{\mathrm{H}}(T,X)=\max\{d_{\mathrm{GH}}(T,X),\vec{d}_{\mathrm{H}}(\partial T% ,X)\}$ . All of the results in our paper have simple corollaries for two subsets of the tree or graph; we give one such example.

Corollary 9.

Let $T$ be a finite metric tree and let $X,Y\subseteq T$ . For any $\varepsilon\geq d_{\mathrm{H}}(T,Y)$ , if $d_{\mathrm{H}}(X,Y)>\vec{d}_{\mathrm{H}}(\partial T,X)+\varepsilon$ , then $d_{\mathrm{GH}}(X,Y)\geq d_{\mathrm{H}}(X,Y)-2\varepsilon$ .

Proof.

We need only apply the triangle inequality:

	$\displaystyle d_{\mathrm{H}}(X,Y)\leq d_{\mathrm{H}}(T,X)+d_{\mathrm{H}}(T,Y)$
$\displaystyle=$	$\displaystyle\max\left\{d_{\mathrm{GH}}(T,X),\vec{d}_{\mathrm{H}}(\partial T,X% )\right\}+d_{\mathrm{H}}(T,Y)$	by Theorem 8
$\displaystyle\leq$	$\displaystyle\max\left\{d_{\mathrm{GH}}(X,Y)+d_{\mathrm{GH}}(T,Y),\vec{d}_{% \mathrm{H}}(\partial T,X)\right\}+d_{\mathrm{H}}(T,Y)$
$\displaystyle\leq$	$\displaystyle\max\left\{d_{\mathrm{GH}}(X,Y)+d_{\mathrm{H}}(T,Y),\vec{d}_{% \mathrm{H}}(\partial T,X)\right\}+d_{\mathrm{H}}(T,Y)$	$\displaystyle\text{since }d_{\mathrm{GH}}(T,Y)\leq d_{\mathrm{H}}(T,Y)$
$\displaystyle=$	$\displaystyle\max\left\{d_{\mathrm{GH}}(X,Y)+2d_{\mathrm{H}}(T,Y),\vec{d}_{% \mathrm{H}}(\partial T,X)+d_{\mathrm{H}}(T,Y)\right\}$
$\displaystyle\leq$	$\displaystyle\max\left\{d_{\mathrm{GH}}(X,Y)+2\varepsilon,\vec{d}_{\mathrm{H}}% (\partial T,X)+\varepsilon\right\}$	$\displaystyle\text{since }d_{\mathrm{H}}(T,Y)\leq\varepsilon.\$

$\hfill\blacktriangleleft$ As a particular case of Theorem 8, we can provide a closed formula for the Gromov–Hausdorff distance between a segment and a sample of it; see [3] for the proof.

Corollary 10.

Let $X$ be a compact non-empty subset of an interval $I=[a,b]$ . Denote by $c=\min X$ and $d=\max X$ . Then $d_{\mathrm{GH}}(I,X)=\max\left\{\frac{c-a+b-d}{2},d_{\mathrm{H}}([c,d],X)\right\}$ .

5 The case of the circle

Before considering general metric graphs in the following section, in this section we first understand the simplest connected metric graph which is not a tree: the circle $G=S^{1}$ . The authors of [2] showed that $d_{\mathrm{GH}}(S^{1},X)=d_{\mathrm{H}}(S^{1},X)$ for a compact subset $X\subseteq S^{1}$ with $d_{\mathrm{GH}}(S^{1},X)<\frac{\pi}{6}$ . A curious question regarding the optimality of the density constant $\frac{\pi}{6}$ was also posed therein [2, Question 2]. While the constant $\frac{\pi}{6}$ provides a sufficient Gromov–Hausdorff density of a subset $X$ to guarantee the equality of its Hausdorff and Gromov–Hausdorff distances to $S^{1}$ , it turns out this constant is suboptimal. In this section, we show that $\frac{\pi}{3}$ is the optimal constant in the case of the circle. That is, for a subset $X\subseteq S^{1}$ , the density condition $d_{\mathrm{GH}}(S^{1},X)<\frac{\pi}{3}$ implies $d_{\mathrm{GH}}(S^{1},X)=d_{\mathrm{H}}(S^{1},X)$ (Theorem 11), and there is a compact $X\subseteq S^{1}$ with $\frac{\pi}{3}=d_{\mathrm{GH}}(S^{1},X)<d_{\mathrm{H}}(S^{1},X)$ (Theorem 12).

Theorem 11.

For any subset $X\subseteq S^{1}$ , we have $d_{\mathrm{GH}}(S^{1},X)\geq\min\left\{d_{\mathrm{H}}(S^{1},X),\ \tfrac{\pi}{3% }\right\}$ .

Proof.

This proof is closely related to [18, 12]. It suffices to show that if $d_{\mathrm{GH}}(S^{1},X)<\frac{\pi}{3}$ , then $d_{\mathrm{GH}}(S^{1},X)\geq d_{\mathrm{H}}(S^{1},X)$ . Let $f\colon S^{1}\to X$ be a (possibly discontinuous) function. By (3), it suffices to show that if $\frac{1}{2}\mathrm{dis}(f)<\frac{\pi}{3}$ , then $\frac{1}{2}\mathrm{dis}(f)\geq d_{\mathrm{H}}(S^{1},X)$ , or equivalently that $\frac{\varepsilon+\mathrm{dis}(f)}{2}\geq d_{\mathrm{H}}(S^{1},X)$ for all $\varepsilon>0$ sufficiently small. Suppose $\frac{1}{2}\mathrm{dis}(f)<\frac{\pi}{3}$ . Fix $\varepsilon>0$ with $5\varepsilon<2\pi-3\mathrm{dis}(f)$ . Form a finite triangulation $K$ of $S^{1}$ with edges of length less than $\varepsilon$ . Let $K^{(0)}\subseteq S^{1}$ be the vertex set of $K$ . Since adjacent vertices $v_{i},v_{i+1}\in K^{(0)}$ satisfy $d(v_{i},v_{i+1})<\varepsilon$ , we have $d(f(v_{i}),f(v_{i+1}))<\varepsilon+\mathrm{dis}(f)<\pi$ . Hence we can map the edge between $v_{i}$ and $v_{i+1}$ to the unique shortest path in $S^{1}$ between $f(v_{i})$ and $f(v_{i+1})$ , obtaining a continuous map $\overline{f}\colon K\to S^{1}$ .

Figure 2: Proof of Theorem 11: Since

\overline{f}(x)=\overline{f}(-x)

, the shortest paths in

S^{1}

between

f(v_{i}),f(v_{i+1})

and

f(v_{j}),f(v_{j+1})

intersect.

Let $r=\frac{\varepsilon+\mathrm{dis}(f)}{2}$ . Suppose for a contradiction that $X^{r}$ is not equal to all of $S^{1}$ . Then there is an arc of length at least $2r$ in $S^{1}$ that contains no points from $X$ . So $\overline{f}$ is non-surjective, since the image of each edge in $K$ is an edge of length less than $2r$ . Hence $\overline{f}\colon K\to S^{1}$ is a map of degree zero. The Borsuk–Ulam theorem [5, Page 206, Exercise 21] then implies there are antipodal points $x,-x\in K$ with $\overline{f}(x)=\overline{f}(-x)$ . Let $x$ be on the closed edge between $v_{i},v_{i+1}\in K^{(0)}$ , and let $-x$ be on the closed edge between $v_{j},v_{j+1}\in K^{(0)}$ . Since $\overline{f}(x)=\overline{f}(-x)$ , the shortest path in $S^{1}$ between $f(v_{i}),f(v_{i+1})$ intersects the shortest path between $f(v_{j}),f(v_{j+1})$ . Since these paths in $S^{1}$ are of length less than $2r$ , one of $f(v_{i}),f(v_{i+1})$ is at a distance less than $r$ from one of $f(v_{j}),f(v_{j+1})$ , i.e. $d(f(v),f(v^{\prime}))<r$ for some $v\in\{v_{i},v_{i+1}\}$ and $v^{\prime}\in\{v_{j},v_{j+1}\}$ ; see Figure 2. We obtain

\mathrm{dis}(f)>d(v,v^{\prime})-d(f(v),f(v^{\prime}))>(\pi-2\varepsilon)-% \tfrac{\varepsilon+\mathrm{dis}(f)}{2}=\pi-\tfrac{\mathrm{dis}(f)}{2}-\tfrac{5% \varepsilon}{2}.

So $\tfrac{5\varepsilon}{2}>\pi-\frac{3\mathrm{dis}(f)}{2}$ , contradicting the choice of $\varepsilon$ . Hence it must be that $X^{r}=S^{1}$ . Since $\frac{\varepsilon+\mathrm{dis}(f)}{2}=r\geq d_{\mathrm{H}}(S^{1},X)$ for all $\varepsilon>0$ sufficiently small, we are done. $\hfill\blacktriangleleft$

(a) Correspondence

\mathcal{R}\subseteq S^{1}\times X

has a distortion of

\frac{2\pi}{3}

. So,

d_{\mathrm{GH}}(S^{1},X)\leq\frac{\pi}{3}

.

(b)

X=\{a,b,c,d,e,f\}\subseteq S^{1}

with

d_{\mathrm{H}}(S^{1},X)=\frac{\pi}{3}+\varepsilon

.

Figure 3: The configuration of points

X\subseteq S^{1}

is depicted to show the optimal constant for the circle.

We now prove the optimality of $\frac{\pi}{3}$ for the circle, i.e. that $\frac{\pi}{3}$ is also a necessary condition.

Theorem 12.

For any $\varepsilon\in\left(0,\frac{\pi}{6}\right)$ , there exists a nonempty compact subset $X\subseteq S^{1}$ with $d_{\mathrm{H}}(S^{1},X)=\frac{\pi}{3}+\varepsilon$ and $d_{\mathrm{GH}}(S^{1},X)=\frac{\pi}{3}<d_{\mathrm{H}}(S^{1},X)$ .

Proof.

We construct $X$ to be a six-element subset of $S^{1}$ . Both $X$ and a particular correspondence $\mathcal{R}\subseteq S^{1}\times X$ are shown in Figure 3. One can check that $d_{\mathrm{H}}(S^{1},X)=\frac{\pi}{3}+\varepsilon$ . Also, one can check that $\mathrm{dis}(\mathcal{R})=\frac{2\pi}{3}$ , giving $d_{\mathrm{GH}}(S^{1},X)\leq\frac{\pi}{3}$ . So $d_{\mathrm{GH}}(S^{1},X)<d_{\mathrm{H}}(S^{1},X)$ . Moreover, Theorem 11 implies that $d_{\mathrm{GH}}(S^{1},X)=\frac{\pi}{3}$ . $\hfill\blacktriangleleft$

6 Metric graphs with loops with coefficient $1$

In this section, we extend our results for the circle to general metric graphs; see Theorem 23.

6.1 Distortion of continuous maps between graphs

We first need a Borsuk–Ulam theorem for maps into trees; see [3] for the proof.

Lemma 13.

If $T$ is a tree and $f\colon S^{1}\to T$ is continuous, then there exist $x,x^{\prime}\in S^{1}$ with $d(x,x^{\prime})\geq\frac{2\pi}{3}$ and $f(x)=f(x^{\prime})$ .

Note that the lower bound $\frac{2\pi}{3}$ in Lemma 13 cannot be improved, as shown in Figure 4.

Figure 4: The lower bound in Lemma 13 is tight. The function

f

sends the black circle to the blue tripod. The points

a

,

b

and

c

are at distance

\frac{2\pi}{3}

apart and in the same fiber of

f

.

Recall that $G_{0}$ is the core of a metric graph $G$ (see Section 2), and that $e(G_{0})$ is the length of the shortest edge in $G_{0}$ .

Lemma 14.

Let $(G,d)$ be a metric graph and $\gamma$ be a simple loop. If $y,y^{\prime}\in\gamma$ satisfy $d(y,y^{\prime})<\frac{e(G_{0})}{2}$ , then there is a unique geodesic joining $y$ and $y^{\prime}$ and it lies on $\gamma$ .

Proof.

Let $\eta$ be a simple path connecting $y$ and $y^{\prime}$ . If $\eta$ is not entirely in $\gamma$ , its length is at least $e(G_{0})$ . So since $d(y,y^{\prime})<\frac{e(G_{0})}{2}$ , a geodesic connecting the two points must lie on $\gamma$ ; see Figure 5. This geodesic is unique since the length of a loop is at least $e(G_{0})$ . $\hfill\blacktriangleleft$

(a)

(b)

Figure 5: The assumptions in Lemma 14 are necessary. Loop

\gamma

is represented with a dashed red line. (a) If there is no bound on

e(G_{0})

, then there may exist a shorter path connecting

y

and

y^{\prime}

using a shortcut

\eta

. (b) If

\gamma

is not simple, then

y

and

y^{\prime}

may be arbitrarily close and joined by geodesics that are not in

\gamma

.

The following lemma is the crucial step showing that a continuous map between finite graphs must send simple loops to simple loops, provided that the distortion is sufficiently small compared to the length of the shortest internal edge.

Lemma 15.

Let $\overline{f}\colon(G,d_{G})\to(G^{\prime},d_{G^{\prime}})$ be a continuous map between finite metric graphs. Assume that $\tfrac{\mathrm{dis}(\overline{f})}{2}<\tfrac{\min\{e(G_{0}),e(G^{\prime}_{0})% \}}{8}$ . Then $\overline{f}$ induces an injection $\Phi\colon\mathcal{L}(G)\to\mathcal{L}(G^{\prime})$ between the simple loops of $G$ and the simple loops of $G^{\prime}$ as follows: given a simple loop $\gamma\in\mathcal{L}(G)$ , $\Phi(\gamma)$ is the only simple loop of $G^{\prime}$ contained in $\overline{f}(\gamma)$ .

Proof of Lemma 15 $\square$ .

For readability purposes, let us divide the proof into several claims. First, let us show that the map $\Phi$ is well-defined, i.e., for every simple loop $\gamma\in\mathcal{L}(G)$ there is a simple loop of $G^{\prime}$ contained in $\overline{f}(\gamma)$ and that simple loop is unique.

$\vartriangleright$ Claim 16 (Existence).

If $\gamma$ is a simple loop of $G$ , then $\overline{f}(\gamma)$ contains a simple loop of $G^{\prime}$ .

Proof of Claim 16.

Suppose for a contradiction that $\overline{f}(\gamma)$ does not contain a loop. Since $\overline{f}(\gamma)$ is connected, it is a tree. So Lemma 13 applies to give points $x,x^{\prime}\in\gamma$ with $\overline{f}(x)=\overline{f}(x^{\prime})$ and $d_{\gamma}(x,x^{\prime})\geq\tfrac{\mathrm{length}(\gamma)}{3}$ where $d_{\gamma}$ is the geodesic distance on $\gamma$ . We must have $d_{G}(x,x^{\prime})\geq\tfrac{e(G_{0})}{3}$ , since if $d_{G}(x,x^{\prime})<\tfrac{e(G_{0})}{3}<\tfrac{e(G_{0})}{2}$ , then Lemma 14 would give that a geodesic connecting $x$ and $x^{\prime}$ lies on $\gamma$ , and so $d_{G}(x,x^{\prime})=d_{\gamma}(x,x^{\prime})\geq\tfrac{\mathrm{length}(\gamma)% }{3}\geq\tfrac{e(G_{0})}{3}$ . We obtain the contradiction

\mathrm{dis}(\overline{f})\geq|d_{G}(x,x^{\prime})-d_{G^{\prime}}(\overline{f}% (x),\overline{f}(x^{\prime}))|=d_{G}(x,x^{\prime})\geq\tfrac{e(G_{0})}{3}>% \tfrac{e(G_{0})}{4}>\mathrm{dis}(\overline{f}).

Hence $\overline{f}(\gamma)$ must contain a loop. $\hfill\vartriangleleft$

$\vartriangleright$ Claim 17 (Uniqueness).

If $\gamma$ is a simple loop, then $\overline{f}(\gamma)$ contains at most one simple loop.

Proof of Claim 17.

Note that $\overline{f}(\gamma)$ is a closed subset of $G^{\prime}$ since it is the continuous image of a compact subset. Let $H=\overline{f}(\gamma)$ , which is a connected subgraph of $G^{\prime}$ . Furthermore, let $H_{0}$ be the smallest connected subgraph of $G^{\prime}$ containing the union of all simple loops of $H$ . Suppose for a contradiction that $\overline{f}(\gamma)=H$ contains at least two simple loops. Therefore, at least one vertex of $H_{0}$ has degree at least $3$ . We can then consider the canonical graph representation of $H_{0}$ consisting of only vertices of degree at least $3$ . For every $v\in V(H_{0})$ , the closed subset $(\overline{f})^{-1}(v)$ has diameter at most $\mathrm{dis}(\overline{f})<\frac{e(G_{0})}{2}$ . Hence, the convex hull $C_{v}$ of $(\overline{f})^{-1}(v)\cap\gamma$ is well-defined. Furthermore, for every $v,v^{\prime}\in V(H_{0})$ with $v\neq v^{\prime}$ , we have $C_{v}\cap C_{v^{\prime}}=\emptyset$ . Indeed, for $x\in(\overline{f})^{-1}(v)$ and $x^{\prime}\in(\overline{f})^{-1}(v^{\prime})$ with $v\neq v^{\prime}$ , we have

d_{G}(x,x^{\prime})\geq d_{G^{\prime}}(v,v^{\prime})-\mathrm{dis}(\overline{f}% )\geq e(G^{\prime}_{0})-\mathrm{dis}(\overline{f})>\mathrm{dis}(\overline{f})% \geq\max\{\mathrm{diam}C_{v},\mathrm{diam}C_{v^{\prime}}\}.

Let $\lvert V(H_{0})\rvert=n$ and let $\gamma_{1},\dots,\gamma_{n}$ be the non-empty connected components of $\gamma\setminus\bigcup_{v\in V(H_{0})}C_{v}$ . For every $i\in\{1,\dots,n\}$ , note that $\overline{f}(\gamma_{i})$ is contained in a connected component of $H\setminus V(H_{0})$ .

Figure 6: A representation of the objects constructed in the proof of Claim 17.

Let $\eta_{1},\dots,\eta_{m}$ be the connected components of $H_{0}\setminus V(H_{0})$ . Note that each $\eta_{j}$ is an open-ended path in $H_{0}$ . We claim that $\eta_{j}\cap\overline{f}(\gamma_{1}\cup\cdots\cup\gamma_{n})\neq\emptyset$ for every $j\in\{1,\dots,m\}$ . Let $y$ be the midpoint of $\eta_{j}$ . Since $H=\overline{f}(\gamma)$ , there is $z\in\gamma$ such that $\overline{f}(z)=y$ . For every $v\in V(H_{0})$ and every $x\in(\overline{f})^{-1}(v)$ ,

d_{G}(z,x)\geq d_{G^{\prime}}(y,v)-\mathrm{dis}(\overline{f})\geq\tfrac{e(G^{% \prime}_{0})}{2}-\mathrm{dis}(\overline{f})>2\mathrm{dis}(\overline{f})-% \mathrm{dis}(\overline{f})=\mathrm{dis}(\overline{f})\geq\mathrm{diam}C_{v}.

Hence, $z\notin C_{v}$ and so $z\in\gamma_{1}\cup\cdots\cup\gamma_{n}$ . So far, we have shown that each $\overline{f}(\gamma_{i})$ , for $i\in\{1,\dots,n\}$ , is contained in some connected component of $H\setminus V(H_{0})$ . Furthermore, among these connected components, each $\eta_{j}$ with $j\in\{1,\dots,m\}$ contains the $\overline{f}$ -image of at least one $\gamma_{i}$ . It will be a contradiction if we prove that $n<m$ . Note that the set $\{\eta_{j}\}_{j=1}^{m}$ is in bijection with the edge set $E(H_{0})$ of $H_{0}$ . Hence

2m=2\lvert E(G^{\prime}_{0})\rvert=\sum_{v\in V(G^{\prime}_{0})}\deg_{G^{% \prime}_{0}}(v)\geq 3\lvert V(G^{\prime}_{0})\rvert=3n,

giving the contradiction $n<m$ . It must be that $\overline{f}(\gamma)$ contains at most one simple loop. $\hfill\vartriangleleft$ According to Claims 16 and 17, map $\Phi$ is well-defined. Lastly, we show that it is injective.

$\vartriangleright$ Claim 18.

The map $\Phi\colon\mathcal{L}(G)\to\mathcal{L}(G^{\prime})$ is injective.

Proof of Claim 18.

Let $\gamma_{1}$ , $\gamma_{2}$ , and $\eta$ be three simple loops such that $\eta\subseteq\overline{f}(\gamma_{1})\cap\overline{f}(\gamma_{2})$ . Suppose, by contradiction, that the simple loops $\gamma_{1}$ and $\gamma_{2}$ are distinct, meaning they differ by at least one edge. Without loss of generality, let us fix an edge $e\in E(G)$ that is contained in $\gamma_{1}$ but whose interior is disjoint from $\gamma_{2}$ . Fix the midpoint $m$ of $e$ . In particular, $d_{G}(m,\gamma_{2})\geq\frac{e(G_{0})}{2}$ .

Figure 7: A representation of the objects constructed in the proof of Claim 18.

Let us estimate $d_{G}(m,(\overline{f})^{-1}(\eta))$ . Suppose that $x\in(\overline{f})^{-1}(\eta)$ , and fix $y\in\gamma_{2}$ such that $\overline{f}(x)=\overline{f}(y)$ . Note that $d_{G}(x,y)\leq\mathrm{dis}(\overline{f})$ . Using the triangle inequality, we obtain

	$\displaystyle d_{G}(m,x)$	$\displaystyle\geq d_{G}(m,y)-d_{G}(x,y)\geq d_{G}(m,\gamma_{2})-\mathrm{dis}(% \overline{f})$		(4)
		$\displaystyle\geq\tfrac{e(G_{0})}{2}-\mathrm{dis}(\overline{f})>2\mathrm{dis}(% \overline{f})-\mathrm{dis}(\overline{f})=\mathrm{dis}(\overline{f}).$		(4)

Hence $d(m,(\overline{f})^{-1}(\eta))\geq\mathrm{dis}(\overline{f})$ , and in particular, $\overline{f}(m)\notin\eta$ . Consider the connected component $C$ of $\gamma_{1}\setminus(\overline{f})^{-1}(\eta)$ containing $m$ . Since $(\overline{f})^{-1}(\eta)$ is closed by continuity, $C$ is an open arc in $\gamma_{1}$ . Let $x_{1}$ and $x_{2}$ be the two points of $\gamma_{1}$ on the boundary of $C$ . Note that they both belong to $(\overline{f})^{-1}(\eta)$ , and so $d_{G}(m,x_{i})>\mathrm{dis}(\overline{f})$ by (4). Let us estimate $d_{G}(x_{1},x_{2})$ . A geodesic connecting $x_{1}$ and $x_{2}$ satisfies one of the following:

(i)

either it passes through $m$ ,
(ii)

or it crosses $(\overline{f})^{-1}(\eta)\cap\gamma_{1}$ ,
(iii)

or it uses an edge that is not in $\gamma_{1}$ .

In all three cases, we have $d_{G}(x_{1},x_{2})>\mathrm{dis}(\overline{f})$ . For (i), this follows since $d_{G}(m,x_{i})>\mathrm{dis}(\overline{f})$ . For (ii), let $A\coloneqq(\overline{f})^{-1}(\eta)\cap\gamma_{1}$ . Since $\overline{f}(\gamma_{1})$ contains $\eta$ , we have $\overline{f}(A)=\eta$ . The diameter of $\eta$ is at least $\tfrac{e(G^{\prime}_{0})}{2}$ , and hence $\mathrm{diam}(A)\geq\tfrac{e(G^{\prime}_{0})}{2}-\mathrm{dis}(\overline{f})>2% \mathrm{dis}(\overline{f})-\mathrm{dis}(\overline{f})=\mathrm{dis}(\overline{f})$ .

Finally, we also have $d_{G}(x_{1},x_{2})>\mathrm{dis}(\overline{f})$ in case (iii) since $e(G_{0})>\mathrm{dis}(\overline{f})$ . Since $\overline{f}$ is continuous, $\overline{f}(C)$ is contained in a connected component $D$ of $\overline{f}(\gamma_{1})\setminus\eta$ . Since $\overline{f}(\gamma_{1})$ contains only one loop, $D$ is a tree. Furthermore, $\overline{f}(\gamma_{1})$ is a closed subset of $G^{\prime}$ since it is the continuous image of a compact subset, and it contains only one simple loop. Thus, the closure of $D$ in $G^{\prime}$ intersects $\eta$ in only one point $z$ . We have already observed that $\overline{f}(x_{i})\in\eta$ for $i\in\{1,2\}$ . Furthermore, $\overline{f}(x_{i})$ belongs to the closure of $\overline{f}(C)$ in $G^{\prime}$ , which is contained in the closure of $D$ . Therefore, $\overline{f}(x_{i})=z$ since the latter is the only point in the closure of $D$ that lies on $\eta$ . This gives $\overline{f}(x_{1})=z=\overline{f}(x_{2})$ , which contradicts the above established inequality $d_{G}(x_{1},x_{2})>\mathrm{dis}(\overline{f})$ . $\hfill\vartriangleleft$ This completes the proof of Lemma 15. $\hfill\blacktriangleleft$

6.2 Distortion of arbitrary functions between graphs

To apply Lemma 15 in the context of Gromov–Hausdorff distances, we will need a way to turn arbitrary functions into nearby continuous ones with controlled distortion, as described in the following result.

Lemma 19.

Let $f\colon(G,d_{G})\to(G^{\prime},d_{G^{\prime}})$ be a function between finite metric graphs with distortion $\tfrac{\mathrm{dis}(f)}{2}<r<\tfrac{\min\{e(G_{0}),e(G^{\prime}_{0})\}}{4}$ . Then there is a continuous map $\overline{f}\colon G\to G^{\prime}$ such that $\tfrac{\mathrm{dis}(\overline{f})}{2}<2r$ and $\overline{f}(G)\subseteq(f(G))^{r}$ .

Proof.

We organize the proof into three steps, to help its readability. Let $\varepsilon>0$ satisfy $\varepsilon+\mathrm{dis}(f)<2r$ .

Step 1: Construct a continuous map $\overline{f}$ .

Fix a finite triangulation $K$ of $G$ with edges of length at most $\varepsilon$ such that $V(G)\subseteq K^{(0)}$ . Let us construct a continuous map $\overline{f}\colon K\to G^{\prime}$ as follows. For every vertex $x\in K^{(0)}$ , set $\overline{f}(x)=f(x)$ . Consider now two adjacent vertices $x$ and $y$ in $K^{(0)}$ . Send the segment from $x$ to $y$ to the geodesic segment connecting $f(x)$ and $f(y)$ at uniform speed. The geodesic between the two points $f(x)$ and $f(y)$ is unique since $d_{G^{\prime}}(f(x),f(y))\leq\varepsilon+\mathrm{dis}(f)<\tfrac{e(G^{\prime}_{% 0})}{2}$ .

Step 2: Estimate the distortion of $\overline{f}$ .

We claim that $\mathrm{dis}(\overline{f})\leq 2(\mathrm{dis}(f)+\varepsilon)<4r$ . The second inequality is trivial. Let $x,y\in K$ . Choose a closest point $x_{i}\in K^{(0)}$ to $x$ . Let $x_{i+1}\in K^{(0)}$ be such that $x$ is contained in the edge $\{x_{i},x_{i+1}\}$ . Note that $d_{G}(x,x_{i})\leq\tfrac{\varepsilon}{2}$ . Thus, by construction of $\overline{f}$ ,

d_{G^{\prime}}(\overline{f}(x),f(x_{i}))\leq\frac{d_{G^{\prime}}(f(x_{i}),f(x_% {i+1}))}{2}\leq\frac{\varepsilon+\mathrm{dis}(f)}{2}

(5)

Similarly, if $y_{j}\in K^{(0)}$ is a closest point to $y$ , $d_{G}(y,y_{j})\leq\tfrac{\varepsilon}{2}$ and $d_{G^{\prime}}(\overline{f}(y),f(y_{j}))\leq\tfrac{\varepsilon+\mathrm{dis}(f)% }{2}.$ By applying the triangle inequality, we obtain the following chain of inequalities:
$\displaystyle d_{G^{\prime}}(\overline{f}(x),\overline{f}(y))\leq d_{G^{\prime% }}(\overline{f}(x),\overline{f}(x_{i}))+d_{G^{\prime}}(f(x_{i}),f(y_{j}))+d_{G% ^{\prime}}(\overline{f}(y_{j}),\overline{f}(y))$ $\displaystyle\leq\tfrac{\mathrm{dis}(f)+\varepsilon}{2}+d_{G}(x_{i},y_{j})+% \mathrm{dis}(f)+\tfrac{\mathrm{dis}(f)+\varepsilon}{2}\leq 2\mathrm{dis}(f)+% \varepsilon+d_{G}(x_{i},x)+d_{G}(x,y)+d_{G}(y,y_{j})$ $\displaystyle\leq 2(\mathrm{dis}(f)+\varepsilon)+d_{G}(x,y)<4r+d_{G}(x,y).$

With similar computations, we can show that $d_{G}(x,y)-d_{G^{\prime}}(\overline{f}(x),\overline{f}(y))\leq 2(\mathrm{dis}(% f)+\varepsilon)<4r$ . This proves $\tfrac{\mathrm{dis}(\overline{f})}{2}<2r$ .

Step 3: Show $\overline{f}(K)\subseteq(f(G))^{r}$ .

For every point $\overline{f}(x)\in\overline{f}(K)$ , choose a closest point $x_{i}\in K^{(0)}$ to $x$ as in Step 2. According to (5), $d_{G^{\prime}}(\overline{f}(x),f(x_{i}))<r$ since $\varepsilon+\mathrm{dis}(f)<2r$ . $\hfill\blacktriangleleft$ We finally obtain that the core $G_{0}$ of a graph $G$ is preserved by a function with distortion bounded by a fraction of the shortest edge length.

Proposition 20.

Let $G$ be a finite metric graph and let $f\colon G\to G$ be a function with $\tfrac{\mathrm{dis}(f)}{2}<r<\tfrac{e(G_{0})}{16}$ . Then $G_{0}\subseteq f(G_{0})^{r}$ .

Proof.

Let $\overline{f}\colon G\to G$ be the continuous map described in Lemma 19. Then $\tfrac{\mathrm{dis}(\overline{f})}{2}<2r<\tfrac{e(G_{0})}{8}$ . The restriction $\overline{f}|_{G_{0}}\colon G_{0}\to G$ is also continuous and has the same bound on its distortion. We can then apply Lemma 15 to $\overline{f}|_{G_{0}}$ and obtain an injection $\Phi\colon\mathcal{L}(G_{0})\to\mathcal{L}(G)$ . Since $\mathcal{L}(G_{0})=\mathcal{L}(G)$ by construction and these sets are finite, $\Phi$ is a bijection. Hence, every simple loop of $G$ is contained in $\overline{f}(G_{0})\subseteq f(G_{0})^{r}$ according to Lemma 19. Given that $f(G_{0})^{r}$ is connected, it contains $G_{0}$ . $\hfill\blacktriangleleft$ As an immediate consequence of Proposition 20 we obtain that the Hausdorff and the Gromov–Hausdorff distances between a graph with no leaves and a subset thereof coincide, provided that the latter is sufficiently small.

Corollary 21.

Let $G$ be a finite metric graph with no leaves, and let $X\subseteq G$ . If $d_{\mathrm{GH}}(G,X)<\tfrac{e(G_{0})}{16}$ , then $d_{\mathrm{GH}}(G,X)=d_{\mathrm{H}}(G,X)$ .

Proof.

Let $r>0$ satisfy $d_{\mathrm{GH}}(G,X)<r<\tfrac{e(G_{0})}{16}$ . Then there is a map $f\colon G\to X$ whose distortion satisfies $\tfrac{\mathrm{dis}(f)}{2}<r<\tfrac{e(G_{0})}{16}$ . We can apply Proposition 20 to obtain that $G=G_{0}\subseteq f(G_{0})^{r}\subseteq X^{r}$ . Hence $d_{\mathrm{H}}(G,X)\leq r$ . Since $r$ can be taken arbitrarily, we have $d_{\mathrm{H}}(G,X)\leq d_{\mathrm{GH}}(G,X)$ . $\hfill\blacktriangleleft$ We now discuss how to lower bound the Gromov–Hausdorff distance with respect to the Hausdorff distance for graphs with leaves. The first result relies on hypotheses around the subset $X$ of the graph $G$ . More precisely, similarly to the tree case, we request that the subset $X$ is sufficiently close to the leaves of $G$ .

Proposition 22.

Let $(G,d)$ be a finite metric graph and let $f\colon G\to G$ be a (possibly discontinuous) function with $\tfrac{\mathrm{dis}(f)}{2}<\tfrac{e(G_{0})}{16}$ . If $\partial G\neq\emptyset$ , suppose that $d_{\mathrm{H}}(G,f(G))>\vec{d}_{\mathrm{H}}(\partial G,f(G))$ . Then $d_{\mathrm{H}}(G,f(G))\leq\tfrac{\mathrm{dis}(f)}{2}$ .

Proof.

Let $r>0$ satisfy $\tfrac{\mathrm{dis}(f)}{2}<r<\tfrac{e(G_{0})}{16}$ . Let $\overline{x}\in G$ be a point such that the intersection $B(\overline{x},d_{\mathrm{H}}(G,f(G)))\cap f(G)$ is empty. If $\overline{x}\in G_{0}$ , then $\overline{x}\in f(G)^{r}$ according to Proposition 20, and so $d_{\mathrm{H}}(G,f(G))<r$ . Suppose otherwise that $\overline{x}\notin G_{0}$ . Thus, $G\setminus\{\overline{x}\}$ is disconnected, and at least two connected components thereof have non-empty intersection with $X$ by the assumption. We can conclude as in Proposition 7. $\hfill\blacktriangleleft$

Theorem 23.

Let $G$ be a finite connected metric graph and let $X\subseteq G$ . If $\partial G\neq\emptyset$ , suppose $d_{\mathrm{H}}(G,X)>\vec{d}_{\mathrm{H}}(\partial G,X)$ . If $d_{\mathrm{GH}}(G,X)<\tfrac{e(G_{0})}{16}$ , then $d_{\mathrm{GH}}(G,X)=d_{\mathrm{H}}(G,X)$ .

Proof.

As in the proof of Theorem 8, by Lemma 2 we can assume that $X$ is compact by replacing it with its closure $\overline{X}$ if necessary. Suppose, by contradiction, that $d_{\mathrm{GH}}(G,X)<d_{\mathrm{H}}(G,X)$ . By Lemma 4 there is a function $f\colon G\to X$ such that $\tfrac{1}{2}\mathrm{dis}(f)<\min\{d_{\mathrm{H}}(G,X),\tfrac{e(G_{0})}{16}\}$ and $\vec{d}_{\mathrm{H}}(\partial G,X)=\vec{d}_{\mathrm{H}}(\partial G,f(G))$ . Note that $d_{\mathrm{H}}(G,f(G))\geq d_{\mathrm{H}}(G,X)>\vec{d}_{\mathrm{H}}(\partial G% ,X)=\vec{d}_{\mathrm{H}}(\partial G,f(G))$ . We can apply Proposition 22 to obtain a contradiction with the following chain of inequalities: $d_{\mathrm{H}}(G,X)\leq d_{\mathrm{H}}(G,f(G))\leq\tfrac{\mathrm{dis}(f)}{2}% \leq d_{\mathrm{GH}}(G,X)$ . $\hfill\blacktriangleleft$

7 Conclusion and open questions

We have furthered the study of lower bounding the Gromov–Hausdorff distance between a space and a subset by their Hausdorff distance, particularly for metric graphs. This investigation sparks several open questions and new research directions, especially for spaces beyond graphs: (1) Is the density constant $\frac{e(G_{0})}{16}$ in Theorem 23 optimal? (2) Do our results generalize to general length spaces? If so, under what density assumptions? (3) Are there versions of our results that hold for manifolds with boundary? (4) Are there classes of metric spaces (other than graphs) where the Gromov–Hausdorff distance between the space and a dense enough subset equals their Hausdorff distance?

References

[1] Henry Adams, Johnathan Bush, Nate Clause, Florian Frick, Mario Gómez, Michael Harrison, R. Amzi Jeffs, Evgeniya Lagoda, Sunhyuk Lim, Facundo Mémoli, Michael Moy, Nikola Sadovek, Matt Superdock, Daniel Vargas, Qingsong Wang, and Ling Zhou. Gromov–Hausdorff distances, Borsuk–Ulam theorems, and Vietoris–Rips complexes. arXiv preprint, 2023. arXiv:2301.00246.
[2] Henry Adams, Florian Frick, Sushovan Majhi, and Nicholas McBride. Hausdorff vs Gromov–Hausdorff distances. Discrete & Computational Geometry, 2025.
[3] Henry Adams, Sushovan Majhi, Fedor Manin, Žiga Virk, and Nicolò Zava. Lower bounding the Gromov–Hausdorff distance in metric graphs. arXiv:2411.09182.
[4] Pankaj K. Agarwal, Kyle Fox, Abhinandan Nath, Anastasios Sidiropoulos, and Yusu Wang. Computing the Gromov–Hausdorff distance for metric trees. ACM Trans. Algorithms, 14(2), 2018. doi:10.1145/3185466.
[5] Mark Anthony Armstrong. Basic topology. Springer Science & Business Media, 2013.
[6] Martin R Bridson and André Haefliger. Metric spaces of non-positive curvature, volume 319. Springer Science & Business Media, 2011.
[7] L. E. J. Brouwer. Beweis der Invarianz der Dimensionenzahl. Mathematische Annalen, 70(2):161–165, 1911.
[8] L. E. J. Brouwer. Über Abbildung von Mannigfaltigkeiten. Mathematische Annalen, 71(1):97–115, 1911.
[9] Dmitri Burago, Yuri Burago, and Sergei Ivanov. A course in metric geometry, volume 33. American Mathematical Society, Providence, 2001.
[10] Gunnar Carlsson and Facundo Mémoli. Characterization, stability and convergence of hierarchical clustering methods. Journal of Machine Learning Research, 11(47):1425–1470, 2010. doi:10.5555/1756006.1859898.
[11] Frédéric Chazal, Vin de Silva, and Steve Oudot. Persistence stability for geometric complexes. Geometriae Dedicata, 174:193–214, 2014.
[12] Lester Dubins and Gideon Schwarz. Equidiscontinuity of Borsuk–Ulam functions. Pacific Journal of Mathematics, 95(1):51–59, 1981.
[13] David A Edwards. The structure of superspace. In Studies in topology, pages 121–133. Elsevier, 1975.
[14] Mikhael Gromov. Structures métriques pour les variétés Riemanniennes. Textes Mathématiques, 1, 1981.
[15] Michael Harrison and R Amzi Jeffs. Quantitative upper bounds on the Gromov–Hausdorff distance between spheres. arXiv preprint, 2023. arXiv:2309.11237.
[16] Yibo Ji and Alexey A Tuzhilin. Gromov–Hausdorff distance between segment and circle. arXiv preprint, 2021. arXiv:2101.05762.
[17] Nigel J Kalton and Mikhail I Ostrovskii. Distances between Banach spaces. Forum Math., 11:1–17, 1999.
[18] Alejandro Leon. The Gromov–Hausdorff distance between spheres and their boundaries. To appear, 2026.
[19] Sunhyuk Lim, Facundo Mémoli, and Zane Smith. The Gromov–Hausdorff distance between spheres. Geometry & Topology, 27:3733–3800, 2023.
[20] Sushovan Majhi, Jeffrey Vitter, and Carola Wenk. Approximating Gromov–Hausdorff distance in Euclidean space. Computational Geometry, 116:102034, 2024. doi:10.1016/j.comgeo.2023.102034.
[21] Facundo Mémoli. On the use of Gromov–Hausdorff distances for shape comparison, 2007.
[22] Facundo Mémoli. Some properties of Gromov–Hausdorff distances. Discrete & Computational Geometry, 48(2):416–440, 2012. doi:10.1007/S00454-012-9406-8.
[23] Felix Schmiedl. Computational aspects of the Gromov–Hausdorff distance and its application in non-rigid shape matching. Discrete & Computational Geometry, 57(4):854, 2017.
[24] Alexey A Tuzhilin. Who invented the Gromov–Hausdorff distance? arXiv preprint, 2016. arXiv:1612.00728.
[25] Nicolò Zava. Coarse and bi-Lipschitz embeddability of subspaces of the Gromov–Hausdorff space into Hilbert spaces. Algebr. Geom. Topol., 25(8):5153–5174, 2024.

[bib.bib1] [1] Henry Adams, Johnathan Bush, Nate Clause, Florian Frick, Mario Gómez, Michael Harrison, R. Amzi Jeffs, Evgeniya Lagoda, Sunhyuk Lim, Facundo Mémoli, Michael Moy, Nikola Sadovek, Matt Superdock, Daniel Vargas, Qingsong Wang, and Ling Zhou. Gromov–Hausdorff distances, Borsuk–Ulam theorems, and Vietoris–Rips complexes. arXiv preprint, 2023. arXiv:2301.00246.

[bib.bib2] [2] Henry Adams, Florian Frick, Sushovan Majhi, and Nicholas McBride. Hausdorff vs Gromov–Hausdorff distances. Discrete & Computational Geometry, 2025.

[bib.bib3] [3] Henry Adams, Sushovan Majhi, Fedor Manin, Žiga Virk, and Nicolò Zava. Lower bounding the Gromov–Hausdorff distance in metric graphs. arXiv:2411.09182.

[bib.bib4] [4] Pankaj K. Agarwal, Kyle Fox, Abhinandan Nath, Anastasios Sidiropoulos, and Yusu Wang. Computing the Gromov–Hausdorff distance for metric trees. ACM Trans. Algorithms, 14(2), 2018. doi:10.1145/3185466.

[bib.bib5] [5] Mark Anthony Armstrong. Basic topology. Springer Science & Business Media, 2013.

[bib.bib6] [6] Martin R Bridson and André Haefliger. Metric spaces of non-positive curvature, volume 319. Springer Science & Business Media, 2011.

[bib.bib7] [7] L. E. J. Brouwer. Beweis der Invarianz der Dimensionenzahl. Mathematische Annalen, 70(2):161–165, 1911.

[bib.bib8] [8] L. E. J. Brouwer. Über Abbildung von Mannigfaltigkeiten. Mathematische Annalen, 71(1):97–115, 1911.

[bib.bib9] [9] Dmitri Burago, Yuri Burago, and Sergei Ivanov. A course in metric geometry, volume 33. American Mathematical Society, Providence, 2001.

[bib.bib10] [10] Gunnar Carlsson and Facundo Mémoli. Characterization, stability and convergence of hierarchical clustering methods. Journal of Machine Learning Research, 11(47):1425–1470, 2010. doi:10.5555/1756006.1859898.

[bib.bib11] [11] Frédéric Chazal, Vin de Silva, and Steve Oudot. Persistence stability for geometric complexes. Geometriae Dedicata, 174:193–214, 2014.

[bib.bib12] [12] Lester Dubins and Gideon Schwarz. Equidiscontinuity of Borsuk–Ulam functions. Pacific Journal of Mathematics, 95(1):51–59, 1981.

[bib.bib13] [13] David A Edwards. The structure of superspace. In Studies in topology, pages 121–133. Elsevier, 1975.

[bib.bib14] [14] Mikhael Gromov. Structures métriques pour les variétés Riemanniennes. Textes Mathématiques, 1, 1981.

[bib.bib15] [15] Michael Harrison and R Amzi Jeffs. Quantitative upper bounds on the Gromov–Hausdorff distance between spheres. arXiv preprint, 2023. arXiv:2309.11237.

[bib.bib16] [16] Yibo Ji and Alexey A Tuzhilin. Gromov–Hausdorff distance between segment and circle. arXiv preprint, 2021. arXiv:2101.05762.

[bib.bib17] [17] Nigel J Kalton and Mikhail I Ostrovskii. Distances between Banach spaces. Forum Math., 11:1–17, 1999.

[bib.bib18] [18] Alejandro Leon. The Gromov–Hausdorff distance between spheres and their boundaries. To appear, 2026.

[bib.bib19] [19] Sunhyuk Lim, Facundo Mémoli, and Zane Smith. The Gromov–Hausdorff distance between spheres. Geometry & Topology, 27:3733–3800, 2023.

[bib.bib20] [20] Sushovan Majhi, Jeffrey Vitter, and Carola Wenk. Approximating Gromov–Hausdorff distance in Euclidean space. Computational Geometry, 116:102034, 2024. doi:10.1016/j.comgeo.2023.102034.

[bib.bib21] [21] Facundo Mémoli. On the use of Gromov–Hausdorff distances for shape comparison, 2007.

[bib.bib22] [22] Facundo Mémoli. Some properties of Gromov–Hausdorff distances. Discrete & Computational Geometry, 48(2):416–440, 2012. doi:10.1007/S00454-012-9406-8.

[bib.bib23] [23] Felix Schmiedl. Computational aspects of the Gromov–Hausdorff distance and its application in non-rigid shape matching. Discrete & Computational Geometry, 57(4):854, 2017.

[bib.bib24] [24] Alexey A Tuzhilin. Who invented the Gromov–Hausdorff distance? arXiv preprint, 2016. arXiv:1612.00728.

[bib.bib25] [25] Nicolò Zava. Coarse and bi-Lipschitz embeddability of subspaces of the Gromov–Hausdorff space into Hilbert spaces. Algebr. Geom. Topol., 25(8):5153–5174, 2024.

Lower Bounding the Gromov–Hausdorff Distance in Metric Graphs

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Overview of our results

Theorem 8.

Theorem 5.

Theorem 11.

Theorem 23.

Organization of the paper

2 Background and notation

2.1 Metric spaces

2.2 Metric graphs

Definition 1 (Metric Graph).

2.3 Hausdorff distances

2.4 Gromov–Hausdorff distances

2.5 Gromov–Hausdorff distances and compactness

Lemma 2.

2.6 Gromov–Hausdorff distances and connectedness

Lemma 3.

Proof.

2.7 Gromov–Hausdorff distances and graphs

Lemma 4.

Proof.

3 Ratio of 𝒅𝐆𝐇 vs 𝒅𝐇 can be arbitrarily small for metric trees

Theorem 5.

Proof.

4 Metric trees with coefficient 𝟏

Proposition 6.

Proposition 7.

Proof.

Theorem 8.

Proof.

Corollary 9.

Proof.

Corollary 10.

5 The case of the circle

Theorem 11.

Proof.

Theorem 12.

Proof.

6 Metric graphs with loops with coefficient 𝟏

6.1 Distortion of continuous maps between graphs

Lemma 13.

Lemma 14.

Proof.

Lemma 15.

Proof of Lemma 15 □.

⊳ Claim 16 (Existence).

Proof of Claim 16.

⊳ Claim 17 (Uniqueness).

Proof of Claim 17.

⊳ Claim 18.

Proof of Claim 18.

6.2 Distortion of arbitrary functions between graphs

Lemma 19.

Proof.

Step 1: Construct a continuous map 𝒇¯.

Step 2: Estimate the distortion of 𝒇¯.

Step 3: Show 𝒇¯⁢(𝑲)⊆(𝒇⁢(𝑮))𝒓.

Proposition 20.

Proof.

Corollary 21.

Proof.

Proposition 22.

Proof.

Theorem 23.

Proof.

7 Conclusion and open questions

References

3 Ratio of $d_{\mathrm{GH}}$ vs $d_{\mathrm{H}}$ can be arbitrarily small for metric trees

4 Metric trees with coefficient $1$

6 Metric graphs with loops with coefficient $1$

Proof of Lemma 15 $\square$ .

$\vartriangleright$ Claim 16 (Existence).

$\vartriangleright$ Claim 17 (Uniqueness).

$\vartriangleright$ Claim 18.

Step 1: Construct a continuous map $\overline{f}$ .

Step 2: Estimate the distortion of $\overline{f}$ .

Step 3: Show $\overline{f}(K)\subseteq(f(G))^{r}$ .