Labeled Trees Generating Complete, Compact, and Discrete Ultrametric Spaces

Abstract

We investigate the interrelations between labeled trees and ultrametric spaces generated by these trees. The labeled trees, which generate complete ultrametrics, totally bounded ultrametrics, and discrete ones, are characterized up to isomorphism. As corollary, we obtain a characterization of labeled trees generating compact ultrametrics and discrete totally bounded ultrametrics. It is also shown that every ultrametric space generated by labeled tree contains a dense discrete subspace.

1 Introduction

The following problem was raised in 2001 by Gelfand: using graph theory describe up to isometry all finite ultrametric spaces [27]. An appropriate representation of finite, ultrametric spaces by monotone trees was proposed by Gurvich and Vyalyi in [23]. A simple geometric description of Gurvich–Vyalyi representing trees was found in [32]. This description allows us effectively use the Gurvich–Vyalyi representation in various problems associated with finite ultrametric spaces. In particular, it leads to a graph-theoretic interpretation of the Gomory–Hu inequality [20]. A characterization of finite ultrametric spaces which are as rigid as possible also was obtained [21] on the basis of the Gurvich–Vyalyi representation. Some other extremal properties of finite ultrametric spaces and related them properties of monotone rooted trees have been found in [19]. The interconnections between the Gurvich–Vyalyi representation and the space of balls endowed with the Hausdorff metric are discussed in [16] (see also [18, 31, 33,34,35]).

The Gurvich–Vyalyi representing trees can be considered as a subclass of finite trees endowed with some special labeling on vertex set. The trees with labeled vertices are studied by many mathematicians and there are a number of interesting results in this directions. In survey [22], Gallian writes that over 200 graph labelings techniques have been studied in over 2800 paper during the past 50 years. In this regards, we only note that in almost all studies of trees with labeled vertices, it is assumed that the trees are finite. The infinite trees endowed with positive real labelings on the set of edges are known as the so-called $R$-trees (see [1] for some interesting results related to $R$-trees and ultrametrics). A description of interrelations between finite subtrees of $R$-trees and finite, monotone rooted trees can be found in [17]. The categorical equivalence of trees and ultrametric spaces was investigated in [24] and [28].

Motivated by Gurvich–Vyalyi representation of finite ultrametric spaces and some results of Bruhn, Diestel, Halin, Kühn, Pott, Sprüssel, and Stein [3,4,5, 7,8,9, 11,12,15] on topological aspects of infinite graphs, we consider infinite trees whose vertices are labeled by nonnegative real numbers and ultrametric spaces generated by such trees.

The paper is organized as follows. Sections 2 and 3 contain some necessary concepts and facts from the theory of metric spaces and graph theory, respectively. In Sect. 4, we introduce into consideration the ultrametric spaces $(V(T), d_l)$ generated by non-degenerate vertex labelings $l$ of arbitrary trees $T$. The first main result of the paper is Theorem 2 characterizing, up to isomorphism, the labeled trees $T(l)$ for which the corresponding ultrametric spaces $(V(T), d_l)$ are complete. The characterizations of labeled trees generating discrete ultrametrics and totally bounded ones are found in Theorem 3 and Theorem 4, respectively. Using these results, we describe, up to isomorphism, the labeled trees generating discrete totally bounded ultrametrics in Theorem 5. The final result of Sect. 4 is Theorem 6 characterizing the labeled trees $T(l)$ for which the ultrametric spaces $(V(T), d_l)$ are compact. The last fifth section contains some conjectures and examples related to subject of the paper.

Concluding remarks. The results obtained in the paper indicate a close connection between the combinatorial properties of an infinite tree and the properties of ultrametric spaces generated by labelings on its vertex set.

• A tree $T$ is rayless if and only if every ultrametric generated by vertex labeling is complete (Corollary 4).

• $T$ is locally finite if and only if every ultrametric generated by vertex labeling is discrete (Corollary 5).

• $T$ is rayless, at most countable, and has no adjacent vertices of infinite degree if and only if there is vertex labeling generating a compact ultrametric (Theorem 7).

• $T$ is locally finite if and only if there is vertex labeling generating a discrete totally bounded ultrametric (Corollary 8).

It seems interesting to study similar problems for general infinite connected graphs using the spanning trees technique. Another promising direction of research is the study of ultrametric spaces generated by some special labelings. For example, we can consider the case when the label of a vertex depends on the degree of this vertex.

2 Definitions and Facts from Theory of Metric Spaces

Let us start from basic concepts. In what follows, we will denote by $\mathbb {R}^{+}$ the half-open interval $[0, \infty )$ and write $\mathbb {N}$ for the set of all positive integers, $\{1, 2, \ldots \}$.

A metric on a set X is a function $d:X\times X\rightarrow \mathbb {R}^+$ such that for all $x$, $y$, $z \in X$

• (i) $d(x,y)=d(y,x)$,

• (ii) $(d(x,y)=0)\Leftrightarrow (x=y)$,

• (iii) $d(x,y)\le d(x,z) + d(z,y)$.

A metric space $(X, d)$ is ultrametric if the strong triangle inequality

$$\begin{aligned} d(x,y)\le \max \{d(x,z),d(z,y)\}. \end{aligned}$$

holds for all $x$, $y$, $z \in X$. In this case, the function $d$ is called an ultrametric on $X$.

Definition 1

Let $(X, d)$ and $(Y, \rho )$ be metric spaces. A bijective mapping $\Phi :X \rightarrow Y$ is said to be an isometry if

$$\begin{aligned} d(x,y) = \rho (\Phi (x), \Phi (y)) \end{aligned}$$

holds for all $x$, $y \in X$. The metric spaces are isometric if there is an isometry of these spaces.

Let $(X, d)$ be a metric space. An open ball with a radius $r > 0$ and a center $c \in X$ is the set

$$\begin{aligned} B_r(c) = \{x \in X :d(c, x) < r\}. \end{aligned}$$

We denote by $\mathbf {B}_X$ the set of all open balls in $(X, d)$.

A sequence $(x_n)_{n \in \mathbb {N}} \subseteq X$ is a Cauchy sequence in $(X, d)$ if, for every $r > 0$, there is an integer $n_0 \in \mathbb {N}$ such that $x_n \in B_r(x_{n_0})$ for every $n \geqslant n_0$. It is easy to see that $(x_n)_{n \in \mathbb {N}}$ is a Cauchy sequence if and only if

$$\begin{aligned} \lim _{n \rightarrow \infty } \sup \{d(x_n, x_{n+k}) :k \in \mathbb {N}\} = 0. \end{aligned}$$

Remark 1

Here and later, the symbol $(x_n)_{n\in \mathbb {N}} \subseteq X$ means that $x_n \in X$ holds for every $n \in \mathbb {N}$.

There exists a comfortable “ultrametric modification” of the notion of Cauchy sequence (see, for example, [30, p. 4] or [6, Theorem 1.6, Statement (13)]).

Proposition 1

Let $(X, d)$ be an ultrametric space. A sequence $(x_n)_{n \in \mathbb {N}} \subseteq X$ is a Cauchy sequence if and only if the limit relation

$$\begin{aligned} \lim _{n \rightarrow \infty } d(x_n, x_{n+1}) = 0 \end{aligned}$$

holds.

A sequence $(x_n)_{n \in \mathbb {N}}$ of points in a metric space $(X, d)$ is said to be convergent to a point $a \in X$,

$$\begin{aligned} \lim _{n \rightarrow \infty } x_n = a, \end{aligned}$$

if, for every open ball $B$ containing $a$, it is possible to find an integer $n_0 \in \mathbb {N}$ such that $x_n \in B$ for every $n \geqslant n_0$. Thus, $(x_n)_{n \in \mathbb {N}}$ is convergent to $a$ if and only if

$$\begin{aligned} \lim _{n \rightarrow \infty } d(x_n, a) = 0. \end{aligned}$$

A sequence is convergent if it is convergent to some point. It is clear that every convergent sequence is a Cauchy sequence.

The next proposition follows, for example, from Theorem 6.8.3 in [36].

Proposition 2

Let $(X, d)$ be a metric space and let $(x_n)_{n \in \mathbb {N}} \subseteq X$ be a Cauchy sequence in $(X, d)$. Then, $(x_n)_{n \in \mathbb {N}}$ is convergent if and only if it has a convergent subsequence.

Now, we present a definition of total boundedness.

Definition 2

A subset $A$ of a metric space $(X, d)$ is totally bounded if for every $r > 0$ there is a finite set $\{B_r(x_1), \ldots , B_r(x_n)\} \subseteq \mathbf {B}_X$ such that

$$\begin{aligned} A \subseteq \bigcup _{i = 1}^{n} B_r(x_i). \end{aligned}$$

There exists a simple interdependence between the total boundedness of a set $A \subseteq X$ and Cauchy sequences in $A$.

Proposition 3

A subset $A$ of a metric space $(X, d)$ is totally bounded if and only if every sequence of points of $A$ contains a Cauchy subsequence.

See, for example, Theorem 7.8.2 [36].

Corollary 1

Let $(X, d)$ be a metric space. If $A \subseteq X$ is totally bounded in $(X, d)$ and $C$ is a subset of $A$, then $C$ is totally bounded in $(A, d|_{A \times A})$.

The next basic for us concept is the concept of completeness.

Definition 3

A metric space $(X, d)$ is complete if for every Cauchy sequence $(x_n)_{n \in \mathbb {N}} \subseteq X$ there is a point $a \in X$ such that

$$\begin{aligned} \lim _{n \rightarrow \infty } x_n = a. \end{aligned}$$

Thus, a metric space is complete if and only if the set of Cauchy sequences coincides with the set of convergent sequences in this space.

An important subclass of complete metric spaces is the class of compact metric spaces.

Definition 4

(Borel–Lebesgue property). Let $(X, d)$ be a metric space. A subset $A$ of $X$ is compact if every family $\mathcal {F} \subseteq \mathbf {B}_X$ satisfying the inclusion

$$\begin{aligned} A \subseteq \bigcup _{B \in \mathcal {F}} B \end{aligned}$$

contains a finite subfamily $\mathcal {F}_0 \subseteq \mathcal {F}$ such that

$$\begin{aligned} A \subseteq \bigcup _{B \in \mathcal {F}_0} B. \end{aligned}$$

A standard definition of compactness usually formulated as: every open cover of $A$ in $X$ has a finite subcover.

The following classical theorem was proved by Frechet and it is a “compact” analog of Proposition 3.

Proposition 4

(Bolzano–Weierstrass property). A subset $A$ of a metric space is compact if and only if every sequence of points of $A$ contains a subsequence which converges to a point of $A$.

The next corollary shows that the class of compact metric spaces is the intersection of the class of complete metric spaces with the class of totally bounded ones.

Corollary 2

(Spatial Criterion). A metric space is compact if and only if this space is complete and totally bounded.

This and other criteria of compactness can be found, for example, in [36, p. 206].

Let $(X, d)$ be a metric space and let $S \subseteq X$. The set $S$ is said to be dense in $(X, d)$ if for every $a \in X$ there is a sequence $(s_n)_{n\in \mathbb {N}} \subseteq S$ such that

$$\begin{aligned} a = \lim _{n \rightarrow \infty } s_n. \end{aligned}$$

Recall that a point $p$ of a metric space $(X, d)$ is isolated if there is $\varepsilon > 0$ such that $d(p, x) > \varepsilon$ for every $x \in X {\setminus } \{p\}$. If $p$ is not an isolated point of $X$, then $p$ is called an accumulation point of $X$. We say that a set $A \subseteq X$ is discrete if all points of $A$ are isolated.

It will be shown in Proposition 8 of Sect. 4 that every ultrametric space, generated by labeled graph, contains a dense discrete subset.

3 Definitions and Facts from Graph Theory

A graph is a pair (V, E) consisting of a set V and a set E whose elements are unordered pairs $\{u, v\}$ of different points $u$, $v \in V$. For a graph $G=(V,E)$, the sets $V=V(G)$ and $E=E(G)$ are called the set of vertices and the set of edges, respectively. A graph $G$ is finite if $V(G)$ is a finite set. If $\{x,y\} \in E(G)$, then the vertices $x$ and $y$ are called adjacent. In what follows, we will always assume that $E(G) \cap V(G) = \varnothing$.

Recall that a graph $G_1$ is a subgraph of a graph $G$ if

$$\begin{aligned} V(G_1) \subseteq V(G) \quad \text {and} \quad E(G_1) \subseteq E(G). \end{aligned}$$

In this case, we will write $G_1 \subseteq G$. If $\{G_i :i \in I\}$ is a family of subgraphs of a graph $G$, then, by definition, the union $\bigcup _{i \in I} G_i$ is a subgraph $G^{*}$ of $G$ such that

$$\begin{aligned} V(G^{*}) = \bigcup _{i \in I} V(G_i) \quad \text {and} \quad E(G^{*}) = \bigcup _{i \in I} E(G_i). \end{aligned}$$

Similarly, the intersection $\bigcap _{i \in I} G_i$ is a subgraph $G_{*}$ of $G$ with

$$\begin{aligned} V(G_{*}) = \bigcap _{i \in I} V(G_i) \quad \text {and} \quad E(G_{*}) = \bigcap _{i \in I} E(G_i). \end{aligned}$$

(1)

Let $v^*$ be a vertex of a graph $G$. The neighborhood $N(v^*) = N_G(v^{*})$ is a subgraph of $G$ induced by all vertices adjacent to $v^{*}$. Thus, we have

$$\begin{aligned} V(N(v^{*}))&= \{u \in V(G) :\{u, v^{*}\} \in E(G)\},\\ E(N(v^{*}))&= \bigl \{\{u, v\} \in E(G) :u, v \in V(N(v^{*}))\bigr \} \end{aligned}$$

for every graph $G$ and each $v^{*} \in V(G)$. Let $k$ be a cardinal number. The vertex $v$ of a graph $G$ has degree $k$ if

$$\begin{aligned} k = \mathop {\mathrm{card}}V(N(v)). \end{aligned}$$

The degree of $v$ will be denoted as $\delta _{G}(v)$ or simply as $\delta (v)$.

A path is a finite graph $P$ whose vertices can be numbered without repetitions so that

$$\begin{aligned} V(P) = \{x_1, \ldots , x_k\} \quad \text {and} \quad E(P) = \{\{x_1, x_2\}, \ldots , \{x_{k-1}, x_k\}\} \end{aligned}$$

(2)

with $k \geqslant 2$. We will write $P = (x_1, \ldots , x_k)$ or $P = P_{x_1, x_k}$ if $P$ is a path satisfying (2) and said that $P$ is a path joining $x_1$ and $x_k$. A graph $G$ is connected if for every two distinct vertices of $G$ there is a path $P \subseteq G$ joining these vertices.

A finite graph $C$ is a cycle if there exists an enumeration of its vertices without repetition such that $V(C) = \{x_1, \ldots , x_n\}$ and

$$\begin{aligned} E(C) = \{\{x_1, x_2\}, \ldots , \{x_{n-1}, x_n\}, \{x_n, x_1\}\} \quad \text {with } n \geqslant 3. \end{aligned}$$

Definition 5

A connected graph $T$ with $V(T) \ne \varnothing$ and without cycles is called a tree.

A tree $T$ is locally finite if the inequality $\delta (v) < \infty$ holds for every $v \in V(T)$.

We shall say that a tree $T$ is a star if there is a vertex $c \in V(T)$, the center of $T$, such that $c$ and $v$ are adjacent for every $v \in V(T) {\setminus } \{c\}$.

An infinite graph $G$ of the form

$$\begin{aligned} V(G) = \{x_1, x_2 \ldots , x_n, x_{n+1}, \ldots \}, \quad E(G) = \{\{x_1, x_2\}, \ldots \{x_n, x_{n+1}\}, \ldots \}, \end{aligned}$$

where all $x_n$ are assumed to be distinct, is called a ray [10]. It is clear that every ray is a tree. A graph is rayless if it contains no rays.

Proposition 5

Every infinite connected graph has a vertex of infinite degree or contains a ray.

For the proof, see Proposition 8.2.1 in [10].

The following statement is well known for finite trees (see, for example, Proposition 4.1 [2]) and is usually considered self-evident for infinite trees.

Lemma 1

In each tree, every two different vertices are connected by exactly one path.

Proof

If $T$ is an infinite tree and $v_1$, $v_2$ are two different vertices of $T$ connected by some paths $P_1 \subseteq T$ and $P_2 \subseteq T$, then the graph $P_1 \cup P_2$ is a finite connected subgraph of $T$. Since $T$ does not have cycles, $P_1 \cup P_2$ is also acyclic. Hence, $P_1 \cup P_2$ is a finite tree and $P_1$, $P_2$ are paths connected $v_1$ and $v_2$ in $P_1 \cup P_2$. Thus, $P_1 = P_2$ holds. $\square$

In the next definition, we introduce an analogue of convex hull for arbitrary trees.

Definition 6

Let $T$ be a tree and let $A$ be a nonempty subset of $V(T)$. A subtree $H_A$ of the tree $T$ is the hull of $A$ if $A \subseteq V(H_A)$ and, for every subtree $T^{*}$ of $T$, the tree $H_A$ is a subtree of $T^{*}$ whenever $A \subseteq V(T^*)$.

Thus, $H_A$ is the smallest subtree of $T$ which contains $A$. We want to make sure that for every tree $T$ and each nonempty $A \subseteq V(T)$ the hull $H_A$ is well defined and unique.

Proposition 6

Let $T$ be a tree, $A$ be a nonempty subset of $V(T)$ and let $\mathcal {F}_A$ be the set of all subtrees $T^{*}$ of $T$ for which the inclusion $A \subseteq V(T^{*})$ holds. Then, the graph $\bigcap _{T^{*} \in \mathcal {F}_A} T^{*}$ is the hull of $A$,

$$\begin{aligned} H_A = \bigcap _{T^{*} \in \mathcal {F}_A} T^{*}. \end{aligned}$$

(3)

Proof

It is clear that $\bigcap _{T^{*} \in \mathcal {F}_A} T^{*}$ is a subgraph of $T^{*}$ for every $T^{*} \in \mathcal {F}_A$. In particular, $\bigcap _{T^{*} \in \mathcal {F}_A} T^{*}$ is a subgraph of $T$ because $T \in \mathcal {F}_A$. Since $T$ is a tree, the subgraph $\bigcap _{T^{*} \in \mathcal {F}_A} T^{*}$ contains no cycles. Hence, to prove (3), it suffices to show that $\bigcap _{T^{*} \in \mathcal {F}_A} T^{*}$ is connected.

Let $u$ and $v$ be distinct vertices of $\bigcap _{T^{*} \in \mathcal {F}_A} T^{*}$ and let $P_{u, v}$ be the path joining $u$ and $v$ in $T$. Then, $u$ and $v$ belong to $V(T^{*})$ for every $T^{*} \in \mathcal {F}_A$. Using Lemma 1, we obtain $P_{u, v} \subseteq T^{*}$ for every $T^{*} \in \mathcal {F}_A$. From (1) with $\mathcal {F} = \mathcal {F}_A$, it follows that the path $P_{u, v}$ is also a subgraph of $\bigcap _{T^{*} \in \mathcal {F}_A} T^{*}$. Thus, $\bigcap _{T^{*} \in \mathcal {F}_A} T^{*}$ is connected as required. $\square$

Example 1

Let $T$ be an infinite tree, let a ray $R$,

$$\begin{aligned} V(R) = \{r_1, r_2, \ldots , r_n, r_{n+1}, \ldots \}, \quad E(R) = \{\{r_1, r_2\}, \ldots , \{r_n, r_{n+1}\}, \ldots \}, \end{aligned}$$

be a subgraph of $T$, and $v$ be a vertex of $T$ such that $v \notin V(R)$. We claim that there is a unique $n(v) \in \mathbb {N}$ such that $r_{n(v)}$ is the only common vertex of $R$ and of the path $P_{r_{n(v)}, v}$ joining $r_{n(v)}$ and $v$ in $T$,

$$\begin{aligned} \{r_{n(v)}\} = V(R) \cap V(P_{r_{n(v)}, v}). \end{aligned}$$

(4)

We first prove the existence of some $n(v) \in \mathbb {N}$ satisfying (4) and show that the graph $R \cup P_{r_{n(v)}, v}$ is the hull in $T$ of the set $A {\mathop {=}\limits ^{\text {def}}} V(R) \cup \{v\}$,

$$\begin{aligned} H_A = R \cup P_{r_{n(v)}, v}. \end{aligned}$$

Let $v \in V(T) {\setminus } V(R)$ be fixed. To find $n(v) \in \mathbb {N}$ satisfying (4) it suffices to consider an arbitrary $u \in V(R)$ and the path $(u^1, \ldots , u^m) \subseteq T$ with $u^1 = u$ and $u^m = v$. Since $u \in V(R)$ and $v \notin V(R)$ hold, there is $m_1 \in \{1, \ldots , m-1\}$ such that $u^{m_1} \in V(R)$ and $u^{j} \notin V(R)$ whenever $j \in \{m_1+1, \ldots , m-1\}$. Consequently, there is $n_1 \in \mathbb {N}$ such that $r_{n_1} = u^{m_1}$. If we set $n(v) {\mathop {=}\limits ^{\text {def}}} n_1$, then (4) holds with $P_{r_{n(v)}, v} {\mathop {=}\limits ^{\text {def}}} (u^{m_1}, \ldots , u^{m})$. Since $P_{r_{n(v)}, v}$ and $R$ are connected and have the common vertex $r_{n(v)}$, the union $R \cup P_{r_{n(v)}, v}$ is a subtree of $T$. It is also clear that

$$\begin{aligned} A \subseteq V(R \cup P_{r_{n(v)}, v}) \end{aligned}$$

holds. Now, Definition 6 implies that $H_A$ is a subtree of $R \cup P_{r_{n(v)}, v}$. If we have

$$\begin{aligned} H_A \ne R \cup P_{r_{n(v)}, v}, \end{aligned}$$

then there is $j \in \{m_1+1, \ldots , m-1\}$ such that $u^{j} \notin V(H_A)$. Lemma 1 and $u^{j} \notin V(H_A)$ imply that $H_A$ is disconnected, contrary to Definition 6. From Proposition 6, it follows that the hull $H_A$ is unique. Consequently, the number $n(v) \in \mathbb {N}$ satisfying (4) is also unique.

In what follows, we will say that $R \cup P_{r_{n(v)}, v}$ is a comb in $T$, $v$ is a tooth of this comb, and $r_{n(v)}$ is the root of the tooth $v$ (see Fig. 1).

Fig. 1

The hull $H_A$ of $A = \{v_5\} \cup \{r_i :i \in \mathbb {N}\}$ is comb in $T$, the vertex $r_3$ is the root of the tooth $v_5$ in this comb

Remark 2

Thus, we always assume that each comb has exactly one tooth with exactly one root. The combs with a large number of teeth are more often used in theory of ultrametric spaces and graph theory (see, for example, the Comb representation of compact ultrametric spaces [26] or the Star-Comb Lemma [10, Lemma 8.2.2]).

Let us recall the concept of labeled trees.

Definition 7

A labeled tree is a pair $(T, l)$, where $T$ is a tree and $l$ is a mapping defined on the set $V(T)$.

We say that $T$ is a free tree corresponding to $(T, l)$ and write $T = T(l)$ instead of $(T, l)$. In what follows, we will consider only the nonnegative real-valued labelings $l:V(T)\rightarrow \mathbb {R}^{+}$.

Before introducing into consideration the concept of isomorphism of labeled trees, it is useful to remind the definition of isomorphism for free trees.

Definition 8

Let $T_1$ and $T_2$ be trees. A bijection $f:V(T_1)\rightarrow V(T_2)$ is an isomorphism of $T_1$ and $T_2$ if

$$\begin{aligned} (\{u,v\} \in E(T_1)) \Leftrightarrow (\{f(u),f(v)\} \in E(T_2)) \end{aligned}$$

is valid for all u, $v \in V(T_1)$. Two trees are isomorphic if there exists an isomorphism of these trees.

For the case of labeled trees, Definition 8 must be modified as follows.

Definition 9

Let $T_i=T_i(l_i)$ be a labeled tree, $i = 1$, $2$. A mapping $f:V(T_1) \rightarrow V(T_2)$ is an isomorphism of $T_1(l_1)$ and $T_2(l_2)$ if it is an isomorphism of the free trees $T_1$ and $T_2$ and the equality

$$\begin{aligned} l_2(f(v))=l_1(v) \end{aligned}$$

holds for every $v \in V(T_1)$.

4 Ultrametrics Generated by Labeled Trees

Let $T = T(l)$ be a labeled tree. Following [17], we define a mapping $d_l :V(T) \times V(T) \rightarrow \mathbb {R}^{+}$ as

$$\begin{aligned} d_l(u, v) = {\left\{ \begin{array}{ll} 0 &{} \text {if } u = v,\\ \max \limits _{v^{*} \in V(P)} l(v^{*}) &{} \text {if } u \ne v, \end{array}\right. } \end{aligned}$$

(5)

where $P$ is the path joining $u$ and $v$ in $T$.

Remark 3

The correctness of this definition follows from Lemma 1.

To formulate the first theorem of this section, we recall the concept of pseudoultrametric space. Let $X$ be a set. A symmetric mapping $d :X \times X \rightarrow \mathbb {R}^{+}$ is a pseudoultrametric on $X$ if

$$\begin{aligned} d(x, x) = 0 \quad \text {and} \quad d(x, y) \leqslant \max \{d(x, z), d(z, y)\} \end{aligned}$$

hold for all $x$, $y$, $z \in X$. Every ultrametric is a pseudoultrametric, but a pseudoultrametric $d$ on a set $X$ is an ultrametric if and only if $d(x, y) > 0$ holds for all distinct $x$, $y \in X$.

The notion of isometries can be extended on pseudoultrametrics as follows. If $(X, d)$ and $(Y, \rho )$ are pseudoultrametric spaces, then a mapping $\Phi :X \rightarrow Y$ is an isometry of $(X, d)$ and $(Y, \rho )$ if $\Phi$ is bijective and

$$\begin{aligned} d(x, y) = \rho (\Phi (x), \Phi (y)) \end{aligned}$$

holds for all $x$, $y \in X$.

Theorem 1

Let $T = T(l)$ be a labeled tree. Then, $(V(T), d_l)$ is a pseudoultrametric space. The function $d_l$ is an ultrametric on $V(T)$ if and only if the inequality

$$\begin{aligned} \max \{l(u_1), l(v_1)\} > 0 \end{aligned}$$

holds for every $\{u_1, v_1\} \in E(T)$.

A proof of Theorem 1 can be obtained by simple modification of the proof of Proposition 3.2 [17].

Proposition 7

Let $T_1 = T_1(l_1)$ and $T_2 = T_2(l_2)$ be labeled trees and let $f\! :\! V(T_1) \rightarrow V(T_2)$ be an isomorphism of these trees. Then, the equality

$$\begin{aligned} d_{l_1}(u, v) = d_{l_2}(f(u), f(v)) \end{aligned}$$

holds for all $u$, $v \in V(T_1)$.

Proof

It directly follows from Definition 9 and formula (5), because if $(v_1, \ldots , v_n)$ is a path joining some distinct $v = v_1$ and $u = v_n$ in $T_1$, then $f(u) \ne f(v)$ holds and $(f(v_1), \ldots , f(v_n))$ is a path joining $f(v)$ and $f(u)$ in $T_2$ and we have the equality

$$\begin{aligned} \left\{ l_1(v_1), \ldots , l_1(v_n)\right\} = \left\{ l_2(f(v_1)), \ldots , l_2(f(v_n))\right\} . \end{aligned}$$

$\square$

Corollary 3

Let $T_1 = T_1(l_1)$ and $T_2 = T_2(l_2)$ be isomorphic labeled trees. Then, the pseudoultrametric spaces $(V(T_1), d_{l_1})$ and $(V(T_2), d_{l_2})$ are isometric.

The converse statement is not valid in general. The following example is a modification of Example 3.1 [17].

Example 2

Let $V = \{v_0, v_1, v_2, v_3, v_4\}$ be a five-point set, and let $S = S(l_S)$ and $P = P(l_P)$ be a labeled star with the center $v_0$ and, respectively, a labeled path such that $V(S) = V(P) = V$, $l_S(v_0) = l_P(v_0) = 1$ and

$$\begin{aligned} l_S(v_i) + 1 = l_P(v_i) = 1 \end{aligned}$$

for $i = 1$, $\ldots$, $4$ (see Fig. 2). Then, for all distinct $u$, $v \in V$, we have

$$\begin{aligned} d_{l_P}(u, v) = d_{l_S}(u, v) = 1. \end{aligned}$$

Thus, the ultrametric spaces $(V, d_{l_P})$ and $(V, d_{l_S})$ coincide, but $P(l_P)$ and $S(l_S)$ are not isomorphic as labeled trees or even as free trees.

Fig. 2

The star $S$ and the path $P$ are not isomorphic as trees, but the labelings $l_S$ and $l_P$ generate the same ultrametric on $V$

Example 2 shows that the properties of ultrametric spaces generated by different labeled trees can be the same. Thus, the following problem naturally arises.

Problem 1

Let $\mathcal {UP}$ be the class of ultrametric spaces with a given property $\mathcal {P}$. What common properties do the labeled trees $T = T(l)$ generating $(V(T), d_l) \in \mathcal {UP}$ have?

Below we will consider this problem in the following cases:

• $\mathcal {P} =$ completeness,

• $\mathcal {P} =$ discreteness,

• $\mathcal {P} =$ total boundedness,

• $\mathcal {P} =$ discreteness + total boundedness,

• $\mathcal {P} =$ compactness,

and in each of these cases, we find the corresponding characteristic properties of generating labeled trees.

Let us start from the completeness.

In what follows, we shall say that a labeling $l :V(T) \rightarrow \mathbb {R}^{+}$ is non-degenerate if the inequality

$$\begin{aligned} \max \{l(u), l(v)\} > 0 \end{aligned}$$

holds for every $\{u, v\} \in E(T)$.

Lemma 2

Let $R$ be a ray, $V(R) = \{v_1, v_2, \ldots , v_n, v_{n+1}, \ldots \}$,

$$\begin{aligned} E(R) = \{\{v_1, v_2\}, \ldots , \{v_n, v_{n+1}\}, \ldots \}, \end{aligned}$$

(6)

and let $l :V(R) \rightarrow \mathbb {R}^{+}$ be a non-degenerate labeling. The sequence $(v_n)_{n \in \mathbb {N}}$ is a Cauchy sequence in the ultrametric space $(V(R), d_l)$ if and only if the limit relation

$$\begin{aligned} \lim _{n \rightarrow \infty } l(v_n) = 0 \end{aligned}$$

(7)

holds.

Proof

By Proposition 1, $(v_n)_{n \in \mathbb {N}}$ is a Cauchy sequence in $(V(R), d_l)$ if and only if

$$\begin{aligned} \lim _{n \rightarrow \infty } d_l(v_n, v_{n+1}) = 0. \end{aligned}$$

(8)

Using (5) and (6), we can rewrite (8) as

$$\begin{aligned} \lim _{n \rightarrow \infty } \left( \max \{l(v_n), l(v_{n+1})\}\right) = 0. \end{aligned}$$

Since all $l(v_n)$ belong to $\mathbb {R}^{+}$, (7) holds if and only if

$$\begin{aligned} \limsup _{n \rightarrow \infty } l(v_n) = 0. \end{aligned}$$

Similarly, (8) is equivalent to

$$\begin{aligned} \limsup _{n \rightarrow \infty } (\max \{l(v_n), l(v_{n+1})\}) = 0. \end{aligned}$$

Now, using the equality

$$\begin{aligned} \limsup _{n \rightarrow \infty } l(v_n) = \limsup _{n \rightarrow \infty } (\max \{l(v_n), l(v_{n+1})\}) \end{aligned}$$

we see that (7) and (8) are equivalent. $\square$

The next lemma will be useful to prove Theorem 2.

Lemma 3

Let $R = R(l)$ be a labeled ray,

$$\begin{aligned} V(R) = \{v_1, v_2, \ldots , v_n, v_{n+1}, \ldots \}, \quad E(R) = \{\{v_1, v_2\}, \ldots , \{v_n, v_{n+1}\}, \ldots \}, \end{aligned}$$

with non-degenerate labeling. Then, the sequence $(v_n)_{n \in \mathbb {N}}$ is a Cauchy sequence in $(V(R), d_l)$ if and only if $(v_n)_{n \in \mathbb {N}}$ contains a subsequence which is Cauchy in $(V(R), d_l)$.

Proof

If $(v_n)_{n \in \mathbb {N}}$ is a Cauchy sequence, then $(v_n)_{n \in \mathbb {N}}$ is a Cauchy subsequence of itself.

Conversely, let $(v_{n_k})_{k \in \mathbb {N}}$,

$$\begin{aligned} 1 \leqslant n_1< n_2< \ldots< n_k< n_{k+1} < \ldots , \end{aligned}$$

be a Cauchy subsequence of $(v_n)_{n \in \mathbb {N}}$. It is easy to see that, for every $m \geqslant n_1$, there is the unique $k(m) \in \mathbb {N}$ such that

$$\begin{aligned} n_{k(m)} \leqslant m < n_{k(m)+1}. \end{aligned}$$

(9)

Let us denote by $P_{v_{n_{k(m)}}, v_{n_{k(m)+1}}}$ the path joining $v_{n_{k(m)}}$ and $v_{n_{k(m)+1}}$ in $R$. From (9), it follows that

$$\begin{aligned} v_m \in V(P_{v_{n_{k(m)}}, v_{n_{k(m)+1}}}). \end{aligned}$$

(10)

Now, using (5) and (10), we obtain

$$\begin{aligned} l(v_m) \leqslant \max \{l(v) :v \in V(P_{v_{n_{k(m)}}, v_{n_{k(m)+1}}})\} = d_l(v_{n_{k(m)}}, v_{n_{k(m)+1}}). \end{aligned}$$

(11)

It is clear that the mapping

$$\begin{aligned} \{n_1, n_1+1, \ldots \} \ni m \mapsto n_{k(m)} \in \mathbb {N}\end{aligned}$$

is increasing and satisfies the limit relation

$$\begin{aligned} \lim _{m \rightarrow \infty } n_{k(m)} = +\infty . \end{aligned}$$

(12)

Proposition 1, (11) and (12) imply

$$\begin{aligned} \limsup _{m \rightarrow \infty } l(v_m) \leqslant \limsup _{m \rightarrow \infty } d_l(v_{n_{k(m)}}, v_{n_{k(m)+1}}) = 0. \end{aligned}$$

Thus, we have

$$\begin{aligned} \lim _{m \rightarrow \infty } l(v_m) = 0, \end{aligned}$$

because $l(v_m) \in \mathbb {R}^{+}$ for every $n \in \mathbb {N}$. Using the last limit relation, we obtain that $(v_n)_{n \in \mathbb {N}}$ is a Cauchy sequence by Lemma 2. $\square$

Lemma 4

Let $T = T(l)$ be a labeled tree with non-degenerate labeling $l :V(T) \rightarrow \mathbb {R}^{+}$ and let $T_1$ be a subtree of $T$ having the labeling $l_1 :V(T_1) \rightarrow \mathbb {R}^{+}$ which is the restriction of $l$ on $V(T_1)$, $l_1 = l|_{V(T_1)}$. Then, the labeling $l_1$ is also non-degenerate and the ultrametric $d_{l_1}$ is the restriction of the ultrametric $d_l$ on the set $V(T_1)$, $d_{l_1} = d_l|_{V(T_1) \times V(T_1)}$.

Proof

It follows from formula (5), Lemma 1 and the definition of trees and subtrees. $\square$

Theorem 2

Let $T = T(l)$ be a labeled tree with non-degenerate labeling. Then, the following conditions are equivalent:

• (i) The ultrametric space $(V(T), d_l)$ is complete.

• (ii) For every ray $R \subseteq T$,

  $$\begin{aligned} V(R) = \{x_1, x_2, \ldots , x_n, x_{n+1}, \ldots \}, \quad E(R) = \{\{x_1, x_2\}, \ldots , \{x_{n}, x_{n+1}\}, \ldots \},\nonumber \\ \end{aligned}$$

  (13)

  we have the inequality

  $$\begin{aligned} \limsup _{n \rightarrow \infty } l(x_n) > 0. \end{aligned}$$

  (14)

Proof

$(i) \Rightarrow ~(ii)$. Let $(V(T), d_l)$ be a complete ultrametric space. We must show that condition (ii) is satisfied. Suppose contrary that there is a ray $R \subseteq T$ such that (13) and $\limsup _{n \rightarrow \infty } l(x_n) = 0$ hold. Since all $l(x_n)$ are nonnegative, the last equality holds if and only if

$$\begin{aligned} \lim _{n \rightarrow \infty } l(x_n) = 0. \end{aligned}$$

(15)

From (15) and (5), it follows that

$$\begin{aligned} \lim _{n \rightarrow \infty } d_l(x_n, x_{n+1}) = \lim _{n \rightarrow \infty } \max \{l(x_n), l(x_{n+1})\} = 0, \end{aligned}$$

because $x_n$ and $x_{n+1}$ are adjacent in $R$ and $R \subseteq T$. Hence, by Proposition 1, the sequence $(x_n)_{n \in \mathbb {N}}$ is a Cauchy sequence in the space $(V(T), d_l)$.

Now, using condition (i) and Definition 3, we can find a point $v^{*} \in V(T)$ satisfying the equality

$$\begin{aligned} \lim _{n \rightarrow \infty } d_l(x_n, v^{*}) = 0. \end{aligned}$$

(16)

If there is $n_0 \in \mathbb {N}$ such that $v^{*} = x_{n_0} \in V(R)$, then, for every $n \geqslant n_0 + 1$, the path $P_{x_{n_0}, x_{n}}$ joining $v^{*}$ and $x_n$ in $T$ contains the edge $\{x_{n_0}, x_{n_0+1}\} \in E(R)$. Since $l :V(T) \rightarrow \mathbb {R}^{+}$ is non-degenerate, (5) and $\{x_{n_0}, x_{n_0+1}\} \in E(P_{x_{n_0}, x_{n_0+1}})$ imply

$$\begin{aligned} d_l(v^{*}, x_n) \geqslant \max \{l(x_{n_0}), l(x_{n_0+1})\} > 0 \end{aligned}$$

for every $n \geqslant n_0 + 1$, contrary to (16).

Suppose now that $v^{*} \in V(T) {\setminus } V(R)$. Then, the hull $H_A$ of the set

$$\begin{aligned} A {\mathop {=}\limits ^{\text {def}}} V(R) \cup \{v^{*}\} \end{aligned}$$

is a comb in $T$ with the tooth $v^{*}$ (see Definition 6 and Example 1). Write $u^{*}$ for the root of $v^{*}$ in $H_A$. Since $u^{*} \ne v^{*}$ and $u^{*}$ is the only common vertex of $R$ and of the path $P_{u^{*}, v^{*}}$ joining $u^{*}$ and $v^{*}$ in $T$, we have

$$\begin{aligned} d_l(x_n, v^{*}) \geqslant d_l(u^{*}, v^{*}) > 0 \end{aligned}$$

for all $x_n \in V(R)$, contrary to (16). Condition (ii) follows.

$(ii) \Rightarrow ~(i)$. Let (ii) hold. We must show that the ultrametric space $(V(T), d_l)$ is complete. According to Definition 3, the space is complete if every Cauchy sequence of points of this space is convergent.

Let us consider an arbitrary Cauchy sequence $(y_n)_{n \in \mathbb {N}} \subseteq V(T)$ and define the range $A$ of $(y_n)_{n \in \mathbb {N}}$ as:

$$\begin{aligned} (v \in A) \Leftrightarrow (\exists n \in \mathbb {N}:y_n = v). \end{aligned}$$

If $A$ is finite, then the sequence $(y_n)_{n \in \mathbb {N}}$ contains an infinite constant subsequence and, consequently, $(y_n)_{n \in \mathbb {N}}$ is convergent by Proposition 2.

Suppose that $A$ is infinite and denote by $H_A$ the hull of $A$ in $T$. Let us prove that $H_A$ is a rayless graph.

Indeed, let a ray $R$,

$$\begin{aligned} V(R) = \{r_1, r_2, \ldots , r_n, r_{n+1}, \ldots \}, \quad E(R) = \{\{r_1, r_2\}, \ldots , \{r_n, r_{n+1}\}, \ldots \}, \end{aligned}$$

be a subgraph of $H_A$. If the intersection $A \cap V(R)$ is infinite, then the sequence $(r_n)_{n \in \mathbb {N}}$ contains a subsequence $(r_{n_k})_{k \in \mathbb {N}}$ which is Cauchy in $(V(T), d_l)$ and, consequently, in $(V(R), d_l|_{V(R) \times V(R)})$. Using Lemmas 3 and  4, we see that the sequence $(r_n)_{n \in \mathbb {N}}$ is Cauchy in $(V(R), d_l|_{V(R) \times V(R)})$. Now, Lemma 4 implies that $(r_n)_{n \in \mathbb {N}}$ is a Cauchy sequence in $(V(T), d_l)$. Moreover, the equality

$$\begin{aligned} \lim _{n \rightarrow \infty } {l(r_n)} = 0 \end{aligned}$$

holds by Lemma 2. The last equality contradicts (14) with $(x_n)_{n \in \mathbb {N}} = (r_n)_{n \in \mathbb {N}}$.

Thus, the intersection $A \cap V(R)$ is finite and $A$ is infinite. We claim that there is an infinite subset $A^{*}$ of the set $A {\setminus } V(R)$ which satisfies the condition:

$(i^{*})$:

If $a_1$, $a_2$ are distinct points of $A^{*}$, and

$$\begin{aligned} A_1 {\mathop {=}\limits ^{\text {def}}} V(R) \cup \{a_1\}, \quad A_2 {\mathop {=}\limits ^{\text {def}}} V(R) \cup \{a_2\}, \end{aligned}$$

and $H_{A_1}$, $H_{A_2}$ are the corresponding hulls of $A_1$ and of $A_2$ in $T$, then the roots $r(a_1)$ and $r(a_2)$ are distinct.

(Recall that the hulls $H_{A_1}$ and $H_{A_2}$ in $T$ are some combs in $T$, see Example 1). To find a desired $A^{*} \subseteq A {\setminus } V(R)$ let us consider a number $N \in \mathbb {N}$ such that

$$\begin{aligned} A \cap V(R) \subseteq \{r_1, r_2, \ldots , r_{N}\} \end{aligned}$$

and suppose that, for every $a \in A {\setminus } V(R)$, the root $r(a)$ of the tooth $a$ in the comb $H_{V(R) \cup \{a\}}$ belongs to the set $\{r_1, r_2, \ldots , r_{N}\}$. The graph

$$\begin{aligned} G_{R, N} {\mathop {=}\limits ^{\text {def}}} (r_1, \ldots , r_{N}) \cup \bigcup _{a \in A \setminus V(R)} P_{a, r(a)}, \end{aligned}$$

where $(r_1, \ldots , r_{N})$ is the path joining $r_1$ and $r_N$ in $R$ and $P_{a, r(a)}$ is the path joining $a$ and $r(a)$ in the comb $H_{V(R) \cup \{a\}}$, is a connected subgraph of $T$ satisfying the conditions

$$\begin{aligned} A \subseteq V(G_{R, N}) \quad \text {and} \quad r_n \notin V(G_{R, N}) \end{aligned}$$

for every $n \geqslant N+1$. Since $r_n \in V(H_A)$ holds for every $n \in \mathbb {N}$, the inclusion

$$\begin{aligned} V(H_A) \subseteq V(G_{R, N}) \end{aligned}$$

is false, contrary to Proposition 6. Hence, there is an element $y_{n_1}$ of the sequence $(y_{n})_{n \in \mathbb {N}}$ such that $y_{n_1} \in A {\setminus } V(R)$ and $r(y_{n_1}) = r_{N_1}$ and $N_1 > N$. If for every $a \in A {\setminus } V(R)$ the root $r(a)$ belongs to $\{r_1, \ldots , r_N, \ldots , r_{N_1}\}$, then repeating the above procedure with the graph $G_{R, N_1}$ gives us $y_{n_2} \in A {\setminus } V(R)$ with $r(y_{n_2}) = r_{N_2}$ such that $n_2 > n_1$ and $N_2 > N_1$ and so on.

Let us consider the sequence $(y_{n_k})_{k \in \mathbb {N}}$, whose elements are inductively defined above, and write

$$\begin{aligned} A^{*} {\mathop {=}\limits ^{\text {def}}} \{y_{n_k} :k \in \mathbb {N}\}. \end{aligned}$$

Then, condition $(i^{*})$ satisfies with this $A^{*}$. Since $(y_{n})_{n \in \mathbb {N}}$ is a Cauchy sequence in $(V(T), d_l)$, the sequence $(y_{n_k})_{k \in \mathbb {N}}$ is also Cauchy. It is easy to prove that the inequality

$$\begin{aligned} d_l(r(y_{n_{k_1}}), r(y_{n_{k_2}})) \leqslant d_l(y_{n_{k_1}}, y_{n_{k_2}}) \end{aligned}$$

(17)

holds for all $k_1$, $k_2 \in \mathbb {N}$ (see Fig. 3). Consequently, $(r(y_{n_k}))_{k \in \mathbb {N}}$ is a Cauchy sequence in $(V(T), d_l)$.

Fig. 3

The path $\bigl (r(y_{n_{k_1}}), \ldots , r(y_{n_{k_2}})\bigr )$ is a subgraph of the path $\bigl (y_{n_{k_1}}, \ldots , r(y_{n_{k_1}}), \ldots , r(y_{n_{k_2}}), \ldots , y_{n_{k_2}}\bigr )$. It implies inequality (17)

Now, using Lemmas 3 and 4, we can prove that the sequence $(r_n)_{n \in \mathbb {N}}$ of all vertices of the ray $R$ is also a Cauchy sequence in $(V(T), d_l)$. Hence, by Lemma 2, we have the equality

$$\begin{aligned} \lim _{n \rightarrow \infty } l(r_n) = 0, \end{aligned}$$

that contradicts condition (ii).

Thus, the hull $H_A$ is rayless. Since $A$ is infinite, $H_A$ has a vertex $v^{*}$ of infinite degree by Proposition 5. To complete the proof it suffices to show that $(y_n)_{n \in \mathbb {N}}$ converges to the point $v^{*}$ in $(V(T), d_l)$,

$$\begin{aligned} \lim _{n \rightarrow \infty } d_l(y_n, v^{*}) = 0. \end{aligned}$$

Let us consider the subgraph $F_{v^{*}}$ obtained from ${H_A}$ by deleting the vertex $v^{*}$,

$$\begin{aligned} V(F_{v^{*}}) = V({H_A}) \setminus \{v^{*}\}, \quad E(F_{v^{*}}) = \{\{u, v\} \in E({H_A}) :u \ne v^{*} \ne v\}. \end{aligned}$$

Since ${H_A}$ is a tree (as a subtree of $T$), $F_{v^{*}}$ is a forest and, for every connected component $T'$ of $F_{v^{*}}$, there is a unique $p\in V(N(v^{*}))$ such that

$$\begin{aligned} p \in V(T'), \end{aligned}$$

(18)

where $N(v^{*})$ is the neighborhood of $v^{*}$ in ${H_A}$. We will write $T^{p}$ for the component $T'$ if (18) holds with $p\in V(N(v^{*}))$.

It is clear that

$$\begin{aligned} H_A = \left( \bigcup _{p \in V(N(v^{*}))} T^{p}\right) \cup S(v^{*}) \end{aligned}$$

(19)

holds, where $S(v^{*})$ is the star with the center $v^{*}$ and the vertex set

$$\begin{aligned} V(S(v^{*})) = V(N(v^{*})). \end{aligned}$$

We claim that the set $V(T^p) \cap A$ is nonempty for every $p \in V(N(v^{*}))$. Indeed, suppose that there is $p^{*} \in V(N(v^{*}))$ such that

$$\begin{aligned} V(T^{p^{*}}) \cap A = \varnothing . \end{aligned}$$

(20)

Let us denote by $S_{p^{*}}$ the graph which is obtained from $S(v^{*})$ by deleting of the vertex $p^{*}$, i.e.,

$$\begin{aligned} V(S_{p^{*}}) = V(S(v^{*})) \setminus \{p^{*}\} \end{aligned}$$

holds and

$$\begin{aligned} \bigl (\{x, y\} \in E(S_{p^{*}})\bigr ) \Leftrightarrow \bigl (\{x, y\} \in E(S(v^{*})) \text { and } x \ne p^{*} \ne y\bigr ) \end{aligned}$$

is valid for all $x$, $y \in V(N(v^{*}))$. Then, $S_{p^{*}}$ is a star with the center $v^{*}$. From (20) it follows that the union

$$\begin{aligned} \left( \bigcup _{\begin{array}{c} p \in V(N(v^{*}))\\ p \ne p^{*} \end{array}} T^{p} \right) \cup S_{p^{*}} \end{aligned}$$

is a subtree of $T$ and the set $A$ is a subset of the vertex set of this subtree. Hence, by Definition 6, we have

$$\begin{aligned} p^{*} \notin V(H_A), \end{aligned}$$

contrary to (19). Using the conditions

$$\begin{aligned} \delta _{H_A} (v^{*}) = \infty \quad \text {and} \quad V(T^{p}) \cap A \ne \varnothing \end{aligned}$$

for every $p \in V(N(v^{*}))$, we can find a subsequence $(y_{n_m})_{m \in \mathbb {N}}$ of the sequence $(y_{n})_{n \in \mathbb {N}}$ such that for every $m \in \mathbb {N}$ there is $p(m) \in V(N(v^{*}))$ satisfying $y_{n_m} \in T^{p}$, and $p(m_1) \ne p(m_2)$ whenever $m_1 \ne m_2$. Then, for every pair of distinct $m_1$, $m_2 \in \mathbb {N}$ the path $P_{y_{n_{m_1}}, y_{n_{m_2}}}$ joining $y_{n_{m_1}}$ and $y_{n_{m_2}}$ in $H_A$ contains the vertex $v^{*}$. Hence, by definition (5), we have the inequality

$$\begin{aligned} d_l\left( y_{n_{m_1}}, y_{n_{m_2}}\right) \geqslant \max \left\{ d_l\left( y_{n_{m_1}}, v^{*}\right) , d_l\left( v^{*}, y_{n_{m_2}}\right) \right\} \end{aligned}$$

(21)

whenever $m_1$, $m_2 \in \mathbb {N}$. By Proposition 2, the sequence $(y_{n})_{n \in \mathbb {N}}$ is convergent if $(y_{n_m})_{m \in \mathbb {N}}$ is convergent. Using Proposition 1 and inequality (21) with $n_{m_1} = n_{m}$ and $n_{m_2} = n_{m+1}$ we obtain

$$\begin{aligned} 0 = \lim _{m \rightarrow \infty } d_l\left( y_{n_{m}}, y_{n_{m+1}}\right) \geqslant \limsup _{m \rightarrow \infty } d_l\left( y_{n_{m}}, v^{*}\right) , \end{aligned}$$

that implies

$$\begin{aligned} \lim _{m \rightarrow \infty } d_l\left( y_{n_{m}}, v^{*}\right) = 0. \end{aligned}$$

Thus, $(y_{n_m})_{m \in \mathbb {N}}$ is convergent to $v^{*}$. $\square$

Condition (ii) of Theorem 2 is vacuously true for every rayless tree $T$. Moreover, if $R \subseteq T$ is a ray satisfying (13), then it is easy to construct a non-degenerate labeling $l :V(T) \rightarrow \mathbb {R}^{+}$ such that (14) does not hold. Thus, Theorem 2 implies the next corollary.

Corollary 4

The following statements are equivalent for every tree $T$:

• (i) The ultrametric space $(V(T), d_{l})$ is complete for every non-degenerate labeling $l :V(T) \rightarrow \mathbb {R}^{+}$.

• (ii) $T$ is rayless.

Recall that a metric space $(X, d)$ is discrete if every point of $X$ is isolated.

Theorem 3

Let $T = T(l)$ be a labeled tree with non-degenerate labeling. Then, the following statements are equivalent:

• (i) The ultrametric space $(V(T), d_{l})$ is discrete.

• (ii) For every $v^{*} \in V(T)$, we have either $l(v^{*}) > 0$ or $l(v^{*}) = 0$ and

  $$\begin{aligned} 0 < \inf _{u \in V(N(v^{*}))} l(u), \end{aligned}$$

  (22)

  where $N(v^{*})$ is the neighborhood of $v^{*}$ in $T$.

Proof

$(i) \Rightarrow ~(ii)$. Let $(V(T), d_{l})$ be a discrete ultrametric space. If (ii) does not hold, then there is a vertex $v^{*}$ such that $l(v^{*}) = 0$ and

$$\begin{aligned} \inf _{u \in V(N(v^{*}))} l(u) = 0. \end{aligned}$$

Hence, there exists a sequence $(u_n)_{n \in \mathbb {N}} \subseteq V(N(v^{*}))$ such that

$$\begin{aligned} \lim _{n \rightarrow \infty } l(u_n) = 0. \end{aligned}$$

The last limit relation, the equality $l(v^{*}) = 0$, equality (5) and the definition of the neighborhoods of vertices of graph imply that

$$\begin{aligned} \lim _{n \rightarrow \infty } d(v^{*}, u_n) = 0 \end{aligned}$$

(23)

holds. Hence, $v^{*}$ is an accumulation point in $(V(T), d_{l})$, contrary to statement (i).

$(ii) \Rightarrow ~(i)$. Let (ii) hold. Statement (i) is valid if $E(T) = \varnothing$. Indeed, in this case the vertex set of $T$ is a single-point set $\{v^{*}\}$. Thus, $V(N(v^{*})) = \varnothing$ holds and, consequently, we have

$$\begin{aligned} \inf _{u \in V(N(v^{*}))} l(u) = \inf _{u \in \varnothing } l(u) = +\infty , \end{aligned}$$

that implies (22). (We consider here the empty set $\varnothing$ as a subset of $[-\infty , \infty ]$ and adopt the standard agreement on the supremum and infimum of empty set.)

Let $E(T) \ne \varnothing$ hold.

Suppose that $v^{*}$ is a vertex of $T$ such that $l(v^{*}) > 0$. Then, (5) implies

$$\begin{aligned} d_l(u, v^{*}) \geqslant l(v^{*}) \end{aligned}$$

for every $u \in V(T) {\setminus } \{v^{*}\}$. Hence, $v^{*}$ is an isolated point of $(V(T), d_{l})$.

Let us consider now the case when $v^{*} \in V(T)$ has the zero label, $l(v^{*}) = 0$, and assume that we have $\delta _{T}(v^{*}) < \infty$. Since the inequality $\max \{l(u), l(v^{*})\} > 0$ holds for every $u \in V(N(v^{*}))$, from $0< \delta _{T}(v^{*}) < \infty$ follows the inequality

$$\begin{aligned} \min _{u \in V(N(v^{*}))} l(u) > 0. \end{aligned}$$

(24)

Let $u_0 \in V(T) {\setminus } \{v^{*}\}$. Then, there is $u^{*} \in V(P_{v^{*}, u_0})$ such that

$$\begin{aligned} u^{*} \in V(N(v^{*})). \end{aligned}$$

(25)

Now, from (5) and (25), it follows that

$$\begin{aligned} d_l(v^{*}, u_0) = \max _{u \in V(P_{v^{*}, u_0})} l(u) \geqslant {d_l(v^{*}, u^{*})} \geqslant \min _{u \in V(N(v^{*}))} l(u) > 0. \end{aligned}$$

Hence, $v^{*}$ is an isolated point of $(V(T), d_{l})$.

Using inequality (22) instead of (24) and repeating the above arguments, we obtain that $v^{*}$ is also isolated for the case $l(v^{*}) = 0$ and $\delta _{T}(v^{*}) = \infty$. Thus, the ultrametric space $(V(T), d_{l})$ is discrete. $\square$

Corollary 5

The following statements are equivalent for every tree $T$:

• (i) The ultrametric space $(V(T), d_{l})$ is discrete for every non-degenerate labeling $l :V(T) \rightarrow \mathbb {R}^{+}$.

• (ii) The tree $T$ is locally finite.

Proposition 8

Let $T$ be a tree. Then, the ultrametric space $(V(T), d_{l})$ contains a dense discrete subset for every non-degenerate $l :V(T) \rightarrow \mathbb {R}^{+}$.

Proof

Let $l :V(T) \rightarrow \mathbb {R}^{+}$ be non-degenerate. It was shown in the second part of the proof of Theorem 3 that $v \in V(T)$ is an isolated point of the ultrametric space $(V(T), d_l)$ if at least one of the conditions:

• $\delta (v) < \infty$,

• $l(v) > 0$,

• $\delta (v) = \infty$, $l(v) = 0$ and $\inf _{u \in V(N(v^{*}))} l(u) > 0$

is valid. Arguing as in the first part of the proof of Theorem 3, we can show that, for every $v$ satisfying conditions $\delta (v) = \infty$ and

$$\begin{aligned} l(v) = 0 = \inf _{u \in V(N(v^{*}))} l(u), \end{aligned}$$

there is a sequence $(u_n)_{n \in \mathbb {N}} \subseteq V(N(v))$ which converges to $v$ (see (23)). Now, it suffices to note that all elements of this sequence are isolated points of $(V(T), d_l)$ because $l(v) = 0$ holds and $l$ is non-degenerate. $\square$

The following result gives us the necessary and sufficient conditions under which the ultrametric space $(V(T), d_l)$ is totally bounded.

Theorem 4

Let $T = T(l)$ be a labeled tree with non-degenerate labeling. Then, the following statements are equivalent:

• (i) The ultrametric space $(V(T), d_{l})$ is totally bounded.

• (ii) The set

  $$\begin{aligned} V_{\varepsilon } = \bigl \{v \in V(T) :l(v) \geqslant \varepsilon \bigr \} \end{aligned}$$

  (26)

  is finite for every $\varepsilon > 0$ and the inequality $\delta _{T}(v) < \infty$ holds whenever $l(v) > 0$.

Proof

$(i) \Rightarrow ~(ii)$. Let (i) hold. Suppose that the set $V_{\varepsilon }$ is infinite for some $\varepsilon > 0$. Using the definition of $d_{l}$ (see (5)), it is easy to prove the inequality

$$\begin{aligned} d_{l}(v_1, v_2) \geqslant \varepsilon \end{aligned}$$

for all distinct $v_1$, $v_2 \in V_{\varepsilon }$. Hence, the subspace $(V_{\varepsilon }, d_{l}|_{V_{\varepsilon } \times V_{\varepsilon }})$ of totally bounded ultrametric space $(V(T), d_{l})$ is not totally bounded, contrary to Corollary 1. Thus, $V_{\varepsilon }$ is finite for every $\varepsilon > 0$.

Assume now that $T$ contains a vertex $v^*$ of infinite degree, $\delta (v^*) = \infty$, and $l(v^{*}) > 0$ holds.

Let $N(v^{*})$ be the neighborhood of $v^{*}$. The equality $\delta _{T}(v^*) = \infty$ implies that $V(N(v^{*}))$ has an infinite cardinality. For all distinct $u_1$, $u_2 \in V(N(v^{*}))$, the unique path joining $u_1$ and $u_2$ in $T$ has the form $(u_1, v^{*}, u_2)$. Hence,

$$\begin{aligned} d_l(u_1, u_2) \geqslant l(v^{*}) > 0 \end{aligned}$$

holds by (5). It implies that the ultrametric space $(V(N(v^{*})), d_l|_{V(N(v^{*})) \times V(N(v^{*}))})$ is not totally bounded, contrary to (i).

$(ii) \Rightarrow ~(i)$. Let (ii) hold. We must show that $(V(T), d_{l})$ is totally bounded. It is clear that $(V(T), d_{l})$ is totally bounded for finite $T$. Let us consider the case when $T$ is infinite.

By Proposition 3, the ultrametric space $(V(T), d_{l})$ is totally bounded if every sequence of vertices of $T$ contains a Cauchy subsequence. Let us consider a sequence $(u_j^0)_{j \in \mathbb {N}}$ of pairwise distinct points of $V(T)$. Let $(\varepsilon _i)_{i \in \mathbb {N}}$ be a decreasing sequence of strictly positive real numbers such that $\lim _{i \rightarrow \infty } \varepsilon _i = 0$. Statement (ii) implies that the set $V_{\varepsilon _{1}}$ is finite. Write $G^{1}$ for the subgraph of $T$ induced by $V(T) {\setminus } V_{\varepsilon _{1}}$, i.e., $V(G^{1}) = V(T) {\setminus } V_{\varepsilon _{1}}$ and

$$\begin{aligned} \bigl (\{u, v\} \in E(G^{1})\bigr ) \Leftrightarrow \bigl (u, v \in V(G^{1}) \text { and } \{u, v\} \in E(T)\bigr ). \end{aligned}$$

Every connected component of $G^{1}$ is a tree. Since $V_{\varepsilon _{1}}$ is a finite set, and $\delta _{T}(v) < \infty$ holds for every $v \in V_{\varepsilon _{1}}$, the number of these components are finite. Since $T$ is an infinite tree, there is an infinite subtree $T^{1}$ of $T$ with $l(v^{1}) < \varepsilon _{1}$ for all $v^{1} \in V(T^{1})$ and such that $(u_{j}^{1})_{j \in \mathbb {N}} \subseteq V(T^{1})$ holds for an infinite subsequence $(u_{j}^{1})_{j \in \mathbb {N}}$ of the sequence $(u_{j}^{0})_{j \in \mathbb {N}} \subseteq V(T)$. Write $u^{1} = u_1^1$.

Let us consider the subgraph $G^{2}$ of $T^{1}$ induced by $V(T^{1}) {\setminus } V_{\varepsilon _{2}}$. As above, the finiteness of $V_{\varepsilon _{2}}$ implies the existence of an infinite tree $T^{2} \subseteq T^{1}$ and a subsequence $(u_{j}^{2})_{j \in \mathbb {N}}$ of the sequence $(u_{j}^{1})_{j \in \mathbb {N}} \subseteq V(T^{1})$ for which $(u_{j}^{2})_{j \in \mathbb {N}} \subseteq V(T^{2})$ holds. Let us write $u^{2} = u_1^2$.

By induction, for every $i \geqslant 2$, we find an infinite connected component $T^{i+1}$ of the subgraph $G^{i+1}$ of $T^{i}$ induced by $V(T^{i}) {\setminus } V_{\varepsilon _{i+1}}$ and a subsequence $(u_{j}^{i+1})_{j \in \mathbb {N}}$ of the sequence $(u_{j}^{i})_{j \in \mathbb {N}}$ such that

$$\begin{aligned} (u_{j}^{i+1})_{j \in \mathbb {N}} \subseteq V(T^{i+1}). \end{aligned}$$

(27)

Write $u^{i+1}$ for the first element $u_{1}^{i+1}$ of this sequence.

Let us consider now the sequence $(u^{i})_{i \in \mathbb {N}}$. It is clear that $(u^{i})_{i \in \mathbb {N}}$ is a subsequence of the original sequence $(u_j^0)_{j \in \mathbb {N}}$. From (27), it follows that

$$\begin{aligned} l(u^{i+1}) < \varepsilon _{i+1} \end{aligned}$$

holds for every $i \in \mathbb {N}$. The last inequality and the limit relation $\lim _{i \rightarrow \infty } \varepsilon _i = 0$ imply

$$\begin{aligned} \lim _{i \rightarrow \infty } l(u^{i}) = 0. \end{aligned}$$

(28)

Moreover, since for every $i \geqslant 2$ the points $u^{i}$ and $u^{i+1}$ are vertices of the tree $T^{i}$ and the inequality $l(v) \leqslant \varepsilon _{i}$ holds for every $v \in V(T^{i})$, formula (5) implies the inequality

$$\begin{aligned} d_{l}(u^{i}, u^{i+1}) \leqslant l(u^{i-1}) \end{aligned}$$

for every $i \geqslant 2$. Now, using Proposition 1 and limit relation (28), we obtain that $(u^{i})_{i \in \mathbb {N}}$ is a Cauchy sequence.

The same reasons show that $(u_j^0)_{j \in \mathbb {N}}$ contains a Cauchy subsequence whenever $(u_j^0)_{j \in \mathbb {N}}$ contains an infinite subsequence of pairwise distinct members.

To complete the proof, we note only that if all subsequences of pairwise distinct members of a sequence are finite, then there is an infinite constant subsequence of that sequence and this constant subsequence obviously is a Cauchy sequence. $\square$

Corollary 6

Let $T = T(l)$ be a labeled tree with non-degenerate labeling. If the ultrametric space $(V(T), d_l)$ is totally bounded, then the set $V(T)$ is at most countable.

Proof

It suffices to show that the inequality

$$\begin{aligned} \delta _{T}(v^*) \leqslant \aleph _0 \end{aligned}$$

(29)

holds for every vertex $v^*$ of $T$, where $\aleph _0$ is the cardinality of $\mathbb {N}$.

Let $(V(T), d_l)$ be totally bounded and let $v^*$ be a vertex of $T$. Inequality (29) follows directly from Theorem 4 if $l(v^*) > 0$. Suppose that $l(v^*) = 0$ holds. Then, for every $\{u, v^*\} \in E(T)$, we have the inequality $l(u) > 0$. Consequently, the vertex set $V(N(v^{*}))$ satisfies the inclusion

$$\begin{aligned} V(N(v^{*})) \subseteq \bigcup _{n \in \mathbb {N}} V_{1/n}, \end{aligned}$$

(30)

where $V_{1/n}$ is defined by (26) with $\varepsilon = 1/n$. By Theorem 4, $V_{1/n}$ is finite for every $n \in \mathbb {N}$. Hence, $\bigcup _{n \in \mathbb {N}} V_{1/n}$ is at most countable. Now, inequality (29) follows from (30). $\square$

Theorem 5

Let $T = T(l)$ be a labeled tree with non-degenerate labeling. Then, the following conditions are equivalent:

• (i) The ultrametric space $(V(T), d_{l})$ is discrete and totally bounded.

• (ii) The tree $T$ is locally finite and the set

  $$\begin{aligned} V_{\varepsilon } = \bigl \{v \in V(T) :l(v) \geqslant \varepsilon \bigr \} \end{aligned}$$

  is finite for every $\varepsilon > 0$.

Proof

$(i) \Rightarrow ~(ii)$. Let (i) hold. Then, the set $V_{\varepsilon }$ is finite for every $\varepsilon > 0$ by Theorem 4.

Assume now that $T$ contains a vertex $v^*$ of infinite degree, $\delta (v^*) = \infty$. Then, using Theorem 4 again, we obtain the equality

$$\begin{aligned} l(v^{*}) = 0. \end{aligned}$$

(31)

By Theorem 3, equality (31) and discreteness of $(V(T), d_{l})$ imply that there is $\varepsilon ^{*} > 0$ such that

$$\begin{aligned} \inf _{u \in V(N(v^{*}))} l(u) \geqslant \varepsilon ^{*}. \end{aligned}$$

Hence, we have the inclusion $V(N(v^{*})) \subseteq V_{\varepsilon ^{*}}$. It was shown above that $V_{\varepsilon }$ is finite for every $\varepsilon > 0$. Consequently, $V(N(v^{*}))$ is also finite as a subset of a finite set, contrary to $\delta _T (v^{*}) = \infty$.

$(ii) \Rightarrow ~(i)$. Let (ii) hold. Then, $T$ is locally finite and, consequently, the ultrametric space $(V(T), d_{l})$ is discrete by Corollary 5. To complete the proof, it suffices to note that $(V(T), d_{l})$ is totally bounded by Theorem 4. $\square$

Corollary 5 and Theorem 5 imply the following.

Corollary 7

Let $T$ be a tree. Then, the following statements are equivalent:

• (i) There is a non-degenerate labeling $l_1 :V(T) \rightarrow \mathbb {R}^{+}$ for which the ultrametric space $(V(T), d_{l_1})$ is discrete and totally bounded.

• (ii) The ultrametric space $(V(T), d_{l})$ is discrete for every non-degenerate labeling $l :V(T) \rightarrow \mathbb {R}^{+}$.

Proof

If (i) holds, then $T$ is locally finite by Theorem 5, that implies (ii) by Corollary 5.

Conversely, suppose that (ii) holds. Then, using Corollary 5 again, we see that $T$ is locally finite. If $T$ is finite, then (i) is trivially valid. Every infinite locally finite tree has countable vertex set. Thus, all vertices of $T$ can be numbered in a sequence $(v_n)_{n \in \mathbb {N}}$ of pairwise different points and we can define a labeling $l_1 :V(T) \rightarrow \mathbb {R}^{+}$ as

$$\begin{aligned} l_1(v_n) = \frac{1}{n} \end{aligned}$$

for every $n \in \mathbb {N}$. Then, $l_1$ is a non-degenerate labeling and $T(l_1)$ satisfies condition (ii) of Theorem 5. Hence, $(V(T), d_{l_1})$ is discrete and totally bounded. $\square$

Using Corollaries 5 and 7 we obtain.

Corollary 8

Let $T$ be a tree. Then, the following statements are equivalent:

• (i) $T$ is locally finite.

• (ii) There is a non-degenerate labeling $l_1 :V(T) \rightarrow \mathbb {R}^{+}$ for which $(V(T), d_{l_1})$ is discrete and totally bounded.

Theorem 6

Let $T = T(l)$ be a labeled tree with non-degenerate labeling. Then, the following statements are equivalent:

• 1. The ultrametric space $(V(T), d_{l})$ is compact.

• 2. The tree $T$ is rayless and the set

  $$\begin{aligned} V_{\varepsilon } = \bigl \{v \in V(T) :l(v) \geqslant \varepsilon \bigr \} \end{aligned}$$

  is finite for every $\varepsilon > 0$ and the inequality $\delta _{T}(v) < \infty$ holds whenever $l(v) > 0$.

Proof

$(i) \Rightarrow ~(ii)$. Let $(V(T), d_{l})$ be a compact ultrametric space. Every compact metric space is totally bounded and complete by Corollary 2. Hence, by Theorem 4, for every $\varepsilon > 0$ the set $V_{\varepsilon }$ is finite, and $\delta _{T}(v) < \infty$ holds for all vertices $v$ with $l(v) > 0$.

Suppose that there is a ray $R \subseteq T$. Then, the completeness of $(V(T), d_{l})$ and Theorem 2 imply the existence of $\varepsilon ^{*} > 0$ and of a sequence $(x_n)_{n \in \mathbb {N}}$ of pairwise distinct vertices of $R$ such that

$$\begin{aligned} \limsup _{n \rightarrow \infty } l(x_n) \geqslant \varepsilon ^{*} > 0. \end{aligned}$$

Thus, the set $\{v \in V(R) :l(v) \geqslant \frac{1}{2} \varepsilon ^{*}\}$ is infinite, contrary to the finiteness of the set $V_{\frac{\varepsilon ^{*}}{2}}$ which contains $\{v \in V(R) :l(v) \geqslant \frac{1}{2} \varepsilon ^{*}\}$.

$(ii) \Rightarrow ~(i)$. Let (ii) hold. Then, (i) follows from the Spatial Criterion (Corollary 2) and Theorems 2, 4. $\square$

Theorem 7

Let $T$ be a tree. Then, the following statements are equivalent:

• (i) $T$ is rayless, and the set $V(T)$ is at most countable, and, for every $\{x, y\} \in E(T)$, at least one from the degrees $\delta (x)$ and $\delta (y)$ is finite.

• (ii) There is a non-degenerate labeling $l_1 :V(T) \rightarrow \mathbb {R}^{+}$ for which the ultrametric space $(V(T), d_{l_1})$ is compact.

Proof

$(i) \Rightarrow ~(ii)$. Let (i) hold. Let us define the subsets $V^F$ and $V^I$ of $V(T)$ as

$$\begin{aligned} V^F {\mathop {=}\limits ^{\text {def}}} \bigl \{v \in V(T) :\delta (v) \text { is finite}\bigr \}, \quad V^I {\mathop {=}\limits ^{\text {def}}} \bigl \{v \in V(T) :\delta (v) \text { is infinite}\bigr \}. \end{aligned}$$

The set $V(T)$ is at most countable. Consequently, there is a labeling $l_1 :V(T) \rightarrow \mathbb {R}^{+}$ such that:

• the set $V_{\varepsilon } = \{v \in V(T) :l_1(v) \geqslant \varepsilon \}$ is finite for every $\varepsilon > 0$;

• the inequality $l_1(u) > 0$ holds for every $u \in V^F$;

• the equality $l_1(w) = 0$ holds for every $w \in V^I$.

These properties of $l_1$ and statement (i) imply the inequality

$$\begin{aligned} \max \bigl \{l_1(x), l_1(y)\bigr \} > 0 \end{aligned}$$

for every $\{x, y\} \in E(T)$. Hence, $l_1 :V(T) \rightarrow \mathbb {R}^{+}$ is a non-degenerate labeling. Thus, $(V(T), d_{l_1})$ is compact by Theorem 6.

$(ii) \Rightarrow ~(i)$. Let $l_1 :V(T) \rightarrow \mathbb {R}^{+}$ be a non-degenerate labeling for which the ultrametric space $(V(T), d_{l_1})$ is compact. Then, from Theorem 6 it follows that $T$ is rayless. Moreover, since every compact metric space is totally bounded, the set $V(T)$ is at most countable by Corollary 6.

To complete the proof it is enough to show that the inequality

$$\begin{aligned} \min \bigl \{\delta (u), \delta (v)\bigr \} < \infty \end{aligned}$$

holds for every $\{u, v\} \in E(T)$. Assume to the contrary that there exists $\{u, v\} \in E(T)$ such that

$$\begin{aligned} \delta (u) = \delta (v) = \aleph _0. \end{aligned}$$

Since $l_1 :V(T) \rightarrow \mathbb {R}^{+}$ is a non-degenerate labeling, $\{u, v\} \in E(T)$ implies

$$\begin{aligned} \max \bigl \{l_1(u), l_1(v)\bigr \} > 0. \end{aligned}$$

Without loss of generality, we may assume that $l_1(v) > 0$. The last inequality, the inequality $\delta (v) > 0$ and Theorem 6 imply that $(V(T), d_{l_1})$ is not compact, contrary to the definition of $l_1 :V(T) \rightarrow \mathbb {R}^{+}$. $\square$

Corollary 4 and Theorem 7 imply the following.

Corollary 9

Let $T$ be a tree. If there is a non-degenerate labeling $l_1 :V(T) \rightarrow \mathbb {R}^{+}$ for which the ultrametric space $(V(T), d_{l_1})$ is compact, then $(V(T), d_{l})$ is complete for every non-degenerate labeling $l :V(T) \rightarrow \mathbb {R}^{+}$.

Remark 4

It is interesting to compare Corollary 9 with the following theorem: “A metrizable topological space $(X, \tau )$ is compact if and only if every metric generated the topology $\tau$ is complete.” This result was proved by Niemytzki and Tychonoff in 1928 [29]. There is also an ultrametric modification of Niemytzki–Tychonoff theorem recently obtained by Yoshito Ishiki [25].

The next corollary follows from Proposition 5 and Theorems 5, 6.

Corollary 10

The following statements are equivalent for every tree $T$:

• (i) There are non-degenerate labelings $l_1 :V(T) \rightarrow \mathbb {R}^{+}$ and $l_2 :V(T) \rightarrow \mathbb {R}^{+}$ such that $(V(T), d_{l_1})$ is a compact ultrametric space and $(V(T), d_{l_2})$ is a discrete totally bounded ultrametric space.

• (ii) $T$ is a finite tree.

5 Some Examples and Conjectures

Let us consider examples of totally bounded non-complete ultrametric spaces, and compact ultrametric spaces generated by labeled trees having infinitely many vertices of infinite degree. To construct these examples, we use the gluing a given set of labeled trees to a fixed labeled tree.

Let $\mathcal {F} = \{T_i(l_i) :i \in I\}$ be a nonempty set of labeled trees $T_i = T_i(l_{i})$ for which

$$\begin{aligned} V(T_{i_1}) \cap V(T_{i_2}) = \varnothing \end{aligned}$$

(32)

holds for all distinct $i_1$, $i_2 \in I$, and let $T^{*} = T^{*}(l^{*})$ be a labeled tree such that $V(T_i) \cap V(T^{*})$ is a single-point set $\{v_i\}$,

$$\begin{aligned} V(T_i) \cap V(T^{*}) = \{v_i\} \end{aligned}$$

(33)

for every $i \in I$. Let us suppose also

$$\begin{aligned} l^{*}(v_i) = l_{i}(v_i) \end{aligned}$$

(34)

for every $i \in I$ if $v_i$ satisfies (33). Then, we define the gluing $\mathcal {F}$ to $T^{*}$ as a labeled graph $T = T(l)$ with

$$\begin{aligned} V(T) {\mathop {=}\limits ^{\mathrm {def}}} V(T^{*}) \cup \left( \bigcup _{i \in I} V(T_i)\right) , \quad E(T) {\mathop {=}\limits ^{\mathrm {def}}} E(T^{*}) \cup \left( \bigcup _{i \in I} E(T_i)\right) \end{aligned}$$

(35)

and $l :V(T) \rightarrow \mathbb {R}$ such that

$$\begin{aligned} l(v) = {\left\{ \begin{array}{ll} l^{*}(v) &{} \text {if } v \in V(T^{*}),\\ l_{i}(v) &{} \text {if } v \in V(T_i) \text { for some } i \in I. \end{array}\right. } \end{aligned}$$

(36)

Using equalities (32)–(36) one can simply show that $T = T(l)$ is a well-defined labeled tree for which the labeling $l$ is non-degenerate if and only if all labelings $l_i$, $i \in I$, and $l^{*}$ are non-degenerate.

Example 3

Let $R^{*} = R^{*}(l^{*})$ be a labeled ray such that $V(R^{*}) = \mathbb {N}$ and

$$\begin{aligned} \bigl (\{m, n\} \in E(R^{*})\bigr ) \Leftrightarrow \bigl (|m-n|=1\bigr ) \end{aligned}$$

for all $m$, $n \in \mathbb {N}$ and, let the equality

$$\begin{aligned} l^{*}(m) = {\left\{ \begin{array}{ll} \frac{1}{m} &{} \text {if m is odd},\\ 0 &{} \text {if m is even} \end{array}\right. } \end{aligned}$$

hold for each $m \in \mathbb {N}$. Moreover, for every even $m \in \mathbb {N}$, we define a labeled star $S_m(l_m)$ with a center $c_m = m$ and suppose that the following conditions hold:

$$\begin{aligned} \quad V(S_m) \cap \mathbb {N}= \{m\}, \quad l_m(c_m) = 0, \end{aligned}$$

and the restriction $l_m|_{V(S_m) {\setminus } \{c_m\}}$ of $l_m$ on the set $V(S_m) {\setminus } \{c_m\}$ is a bijection to the set $\{\frac{1}{mn} :n \in \mathbb {N}\}$; and

$$\begin{aligned} V(S_{m_1}) \cap V(S_{m_2}) = \varnothing \end{aligned}$$

holds for all distinct even $m_1$, $m_1 \in \mathbb {N}$. Then, we can consider the labeled tree $T = T(l)$ obtained by gluing the set

$$\begin{aligned} \{S_m(l_m) :m \in \mathbb {N}\text { and } m \text { is even}\} \end{aligned}$$

to the labeled ray $R^{*}(l^{*})$ (see Fig. 4). The ultrametric space $(V(T), d_l)$ is totally bounded by Theorem 4 but not complete by Theorem 2.

Fig. 4

The tree $T$ has $\aleph _0$ vertices with degree $\aleph _0$ and the ultrametric space $(V(T), d_l)$ is totally bounded but not complete

Example 4

Let $\mathbb {P}$ be the set of all integer prime numbers $p \geqslant 2$ and let $S^{*} = S^{*}(l^{*})$ be the labeled star with the vertex set $V(S^{*}) = \{p \in \mathbb {P}\} \cup \{0\}$, and the center $c^{*} = 0$, and the labeling $l^{*} :V(S^{*}) \rightarrow \mathbb {R}^{+}$ for which $l^*(0) = 0$ and $l^{*} (p) = 1/p$ hold for all $p \in \mathbb {P}$.

For every $p \in \mathbb {P}$, we define a labeled star $S_p = S_p(l_p)$ with a center $c_p$ such that

$$\begin{aligned} V(S_p) \setminus \{c_p\} = \{p^{n} :n \in \mathbb {N}\}, \end{aligned}$$

and

$$\begin{aligned}&c_p \notin \bigcup _{p \in \mathbb {P}} \bigl (V(S_p) \setminus \{c_p\}\bigr ) \cup V(S^{*});\\&l_p(v) = {\left\{ \begin{array}{ll} 0 &{} \text {if } v = c_p,\\ p^{-n} &{} \text {if } v = p^{n} \text { for some } n \in \mathbb {N}; \end{array}\right. } \end{aligned}$$

and $c_{p_1} \ne c_{p_2}$ for all distinct $p_1$, $p_2 \in \mathbb {P}$. Then, we obtain $V(S^{*}) \cap V(S_p) = \{p\}$, and $l^{*} (p) = l_p(p) = 1/p$, and $\delta _{S^{*}} (c^{*}) = \delta _{S_p} (c_p) = \aleph _0$ for every $p \in \mathbb {P}$.

Let us consider the labeled tree $T = T(l)$ which is obtained by gluing the set $\{S_p(l_p) :p \in \mathbb {P}\}$ to $S^{*}(l^{*})$ (see Fig. 5), then the ultrametric space $(V(T), d_l)$ is compact by Theorem 6.

Fig. 5

The tree $T$ has $\aleph _0$ vertices with degree $\aleph _0$ and the ultrametric space $(V(T), d_l)$ is compact

The following simple example shows that the class of finite ultrametric spaces, which are representable in the form $(V(T), d_l)$, is a proper subclass of all finite ultrametric spaces.

Example 5

Let $V = \{v_1, v_2, v_3, v_4\}$ be a four-point set and let an ultrametric $d :V \times V \rightarrow \mathbb {R}^{+}$ satisfy the equalities

$$\begin{aligned} d(v_1, v_2) = d(v_3, v_4) = 1 \end{aligned}$$

(37)

and

$$\begin{aligned} d(v_1, v_3) = d(v_1, v_4) = d(v_2, v_3) = d(v_2, v_4) = 2. \end{aligned}$$

(38)

Let $T = T(l)$ be a labeled tree such that $V(T) = V$. We claim that the ultrametric spaces $(V, d)$ and $(V(T), d_l)$ are not isometric for any non-degenerate labeling $l$. Indeed, if there is a non-degenerate $l :V(T) \rightarrow \mathbb {R}^{+}$ for which $(V, d)$ and $(V(T), d_l)$ are isomorphic, then from (5) and (37) it follows that

$$\begin{aligned} \max _{1 \leqslant i \leqslant 4} l(v_i) \leqslant 1. \end{aligned}$$

The last inequality and (5) imply that $d_l(v, u) \leqslant 1$ holds for all $u$, $v \in V$, contrary to (38).

It seems to be interesting to get a purely metric characterization of ultrametric spaces generated by labeled trees.

Conjecture 1

Let $(X, d)$ be a discrete nonempty totally bounded ultrametric space. Then, the following statements are equivalent:

• (i) There is a labeled tree $T = T(l)$ such that $(V(T), d_l)$ and $(X, d)$ are isometric.

• (ii) For every $B \in \mathbf {B}_{X}$, there are $c \in X$ and $r > 0$ such that

  $$\begin{aligned} B = \{x \in X :d(x, c) = r\} \cup \{c\} \end{aligned}$$

  i.e., the ball $B$ is the sphere $S(c, r) = \{x \in X :d(x, c) = r\}$ with the added center $c$.

In conclusion, we formulate a simple conjecture linking the properties of Cauchy sequences in $(V(T), d_l)$ with the structure of the hull of the range sets of these sequences (cf. Lemma 3).

Conjecture 2

Let $T$ be a tree and let $(v_n)_{n \in \mathbb {N}}$ be a sequence of distinct vertices of $T$. Then, the following conditions are equivalent:

• (i) The hull of the range set of $(v_n)_{n \in \mathbb {N}}$ is a union of a ray with some finite tree.

• (ii) For every non-degenerate $l :V(T) \rightarrow \mathbb {R}$, the existence of Cauchy subsequence in $(v_n)_{n \in \mathbb {N}}$ implies that $(v_n)_{n \in \mathbb {N}}$ is also a Cauchy sequence.