An interval-realized tree and its discrete vertex metric

(The gluing and (H1)-(H3).) Every principal down-set of $P$ is finite and isomorphic to the face poset of the corresponding cell: $P_{\le u}=\{\mathrm{\varnothing },u\}$ for the one-point cell $C_u$, and $P_{\le e}=\{\mathrm{\varnothing },a,b,e\}$ for the edge $e=\{a,b\}$, which is the face poset of the interval $C_e$ with its two vertices. Meets are $u\wedge e=u$ for an incident pair, $e\wedge f=u$ for distinct edges sharing the vertex $u$, and $\mathrm{\varnothing }$ for disjoint edges, distinct vertices or nonincident vertex-edge pairs; also $p\wedge p=p$ and $p\wedge \mathrm{\varnothing }=\mathrm{\varnothing }$. The face isometries satisfy the cocycle condition vacuously (the only nonempty strict chains are $u<e$), the assignment $p\mapsto F_{p,e}$ is the poset isomorphism from $\{a,b,e\}$ onto the nonempty faces of $C_e$, and the intersection condition holds: the cell images are injective and two of them meet exactly in the image of the meet, which for distinct edges sharing a vertex is that vertex and otherwise is empty. Hence $X_{\mathrm{\Gamma }}$ is an isometric polyhedral gluing. Local finiteness (H2): a point of ${\iota }_e(C_e)$ that is not a vertex point lies in that cell alone, and a vertex point lies in its point cell and exactly the cells of the finitely many edges at $u$. Finite shapes (H3): every cell is a point or an interval of one of the finitely many lengths $\{{\mathrm{\ell }}_e:e\in E\}$. Connectedness (H1): order the edges $e_1,\dots ,e_m$ so that each $e_i$ with $i\ge 2$ shares a vertex with ${\bigcup }_{j<i}{e}_j$, which is possible because $\mathrm{\Gamma }$ is connected; each cell inclusion is continuous by the weak-open trace criterion of [F1], so each ${\iota }_{e_i}(C_{e_i})$ is connected [F6], and $Y_i:={\bigcup }_{j\le i}{\iota }_{e_j}(C_{e_j})$ is connected by induction on $i$, since $Y_{i-1}$ and ${\iota }_{e_i}(C_{e_i})$ are connected and meet in the shared vertex [F6]; finally $X_{\mathrm{\Gamma }}={\bigcup }_i{\iota }_{e_i}(C_{e_i})$, because every vertex of $\mathrm{\Gamma }$ is an endpoint of an edge (an isolated vertex would contradict connectedness of $\mathrm{\Gamma }$ with $E\mathrm{\ne }\mathrm{\varnothing }$), so its point cell is a face of an edge cell and its image is already covered. Thus (H1)-(H3) hold, and [F2] gives that $d$ is a metric inducing the weak topology and that $(X_{\mathrm{\Gamma }},d)$ is proper and complete.

(Cutting a leaf edge: the induction claim.) Let $Z$ be the interval realization of a finite tree ${\mathrm{\Gamma }}_0$ with $m_0\ge 1$ edges and positive lengths, with chain metric $d_0$. We prove: there is a function ${\lambda }_0$ on pairs of points of $Z$, defined recursively below, such that (a) for all $x,y$ there is a chain from $x$ to $y$ of length ${\lambda }_0(x,y)$ and every chain from $x$ to $y$ has length at least ${\lambda }_0(x,y)$; (b) for vertices $u,w$ of ${\mathrm{\Gamma }}_0$, ${\lambda }_0(u,w)$ is the sum of the lengths of the edges of the unique reduced path from $u$ to $w$; (c) exactly one geodesic segment joins any two points of $Z$. Base: if $m_0=1$ with edge $e$, then $Z={\iota }_e(C_e)$, all points have coordinates in $[0,{\mathrm{\ell }}_e]$ and the chains are sequences of such coordinates; a chain of $k$ steps has length ${\sum }_i\mathrm{\mid }{t}_{i-1}-t_i\mathrm{\mid }\ge \mathrm{\mid }{t}_x-t_y\mathrm{\mid }$ [F4], with equality for the one-step chain, so (a) holds with ${\lambda }_0(x,y):=\mathrm{\mid }{t}_x-t_y\mathrm{\mid }$; (b) is the case of two vertices, where ${\lambda }_0$ is ${\mathrm{\ell }}_e$ for the two distinct vertices; and for (c), an isometric map $\gamma$ with $\gamma (0)=x$, $\gamma (L)=y$, $L=\mathrm{\mid }x-y\mathrm{\mid }$, satisfies $\mathrm{\mid }\gamma (s)-x\mathrm{\mid }=s$ and $\mathrm{\mid }\gamma (s)-y\mathrm{\mid }=L-s$ at every $s$ [F3], and in the real interval the unique point with these distances is $x$ if $L=0$, and otherwise the one at fraction $s\mathrm{/}L$ from $x$ to $y$ [F4], so $\gamma$ is unique. Step: let $m_0\ge 2$; take a simple path of maximal length in ${\mathrm{\Gamma }}_0$. An endpoint $v$ has no neighbour outside this path (otherwise it extends), and no neighbour on the path except its next vertex $w$ (otherwise there is a cycle); hence $v$ is a leaf. Removing $v$ and $e=\{v,w\}$ leaves a connected acyclic graph ${\mathrm{\Gamma }}_1$ with $m_0-1\ge 1$ edges, since paths between remaining vertices cannot pass through the leaf; the induction hypothesis supplies ${\lambda }_1$ and (a)-(c) for $Z_1:=X_{{\mathrm{\Gamma }}_1}$ with its own chain metric $d_1$; we will prove that $d_1=d_0{\mathrm{\mid }}_{Z_1\times Z_1}$. Label the cell $C_e$ so that $w$ corresponds to ${\mathrm{\ell }}_e$, and write $t_x$ for the coordinate in $[0,{\mathrm{\ell }}_e]$ of $x\in {\iota }_e(C_e)$. Define ${\lambda }_0(x,y):=\mathrm{\mid }{t}_x-t_y\mathrm{\mid }$ if $x,y\in {\iota }_e(C_e)$; ${\lambda }_0(x,y):=({\mathrm{\ell }}_e-t_x)+{\lambda }_1(w,y)$ if $x\in {\iota }_e(C_e)$, $y\in Z_1$; use the symmetric cross formula when $x\in Z_1$, $y\in {\iota }_e(C_e)$, and put ${\lambda }_0(x,y):={\lambda }_1(x,y)$ if $x,y\in Z_1$. The two formulas agree for $x=w\in {\iota }_e(C_e)\cap Z_1$, so ${\lambda }_0$ is well defined on all pairs.

(The induction step, continued.) $Z={\iota }_e(C_e)\cup Z_1$ and ${\iota }_e(C_e)\cap Z_1={\iota }_w(C_w)=\{w\}$: the cell $C_v$ is a face of $C_e$ alone (as $e$ is the only edge at the leaf $v$), and every cell of ${\mathrm{\Gamma }}_1$ meets $C_e$ in the image of the common face, which by the intersection condition is a face of the vertex cell $C_w$, hence contained in $\{w\}$. A chain passing from the leaf interval to $Z_1$ must visit $w$: at its first step leaving that interval the common cell is a cell of ${\mathrm{\Gamma }}_1$, so the departing point lies in both pieces. Reversing a chain gives the same assertion for entry. In a chain with endpoints in $Z_1$, every maximal excursion into the leaf interval therefore starts and ends at $w$; delete these excursions. The remaining chain is in $Z_1$ and has no greater length, so every original chain has length at least $d_1(x,y)={\lambda }_1(x,y)$, and an attaining chain in $Z_1$ gives the reverse bound. Thus $d_0=d_1$ on $Z_1\times Z_1$. For endpoints in the leaf interval, chains staying there have length at least $\mathrm{\mid }{t}_x-t_y\mathrm{\mid }$ by [F4]. A chain leaving it has an initial portion from $x$ to $w$ and a final portion from $w$ to $y$, both in the interval, of total length at least $({\mathrm{\ell }}_e-t_x)+({\mathrm{\ell }}_e-t_y)\ge \mathrm{\mid }{t}_x-t_y\mathrm{\mid }$; all intervening lengths are nonnegative. The one-step chain attains $\mathrm{\mid }{t}_x-t_y\mathrm{\mid }$, hence $d_0(x,y)=\mathrm{\mid }{t}_x-t_y\mathrm{\mid }$ and $d_0(x,w)={\mathrm{\ell }}_e-t_x$. For $x$ in the leaf interval and $y\in Z_1$, split at the first visit to $w$ preceding departure; the initial portion has length at least ${\mathrm{\ell }}_e-t_x$, and the rest has length at least $d_0(w,y)=d_1(w,y)={\lambda }_1(w,y)$. Concatenating the interval segment with an attaining $Z_1$ chain gives equality. The symmetric case follows by reversing chains. This proves (a) and $d_0={\lambda }_0$ without presupposing any restriction identity. For (b): the unique reduced path from the leaf $v$ to a vertex $y$ of ${\mathrm{\Gamma }}_1$ begins with the edge $e$, so the weighted path length from $v$ to $y$ is ${\mathrm{\ell }}_e$ plus the weighted path length from $w$ to $y$, and the remaining vertex pairs lie in ${\mathrm{\Gamma }}_1$; this is exactly the recursion defining ${\lambda }_0$.

(The interval between two points, and geodesic uniqueness.) With the notation of steps 1.2 and 2.1, put $I(x,y):=\{z\in Z:d_0(x,z)+d_0(z,y)=d_0(x,y)\}$. We show by the same induction that $I(x,y)$ is a set on which $z\mapsto d_0(x,z)$ is injective. Base $m_0=1$: all points have coordinates in the interval and $\mathrm{\mid }x-z\mathrm{\mid }+\mathrm{\mid }z-y\mathrm{\mid }=\mathrm{\mid }x-y\mathrm{\mid }$ holds exactly for $z$ between $x$ and $y$ [F4], so $I(x,y)$ is the coordinate segment between $t_x$ and $t_y$, on which $z\mapsto d_0(x,z)=\mathrm{\mid }{t}_x-t_z\mathrm{\mid }$ is injective. Step, case $x,y\in Z_1$: if $z\in {\iota }_e(C_e)$, then by the additivity of step 2.1, $d_0(x,z)+d_0(z,y)=(d_0(x,w)+d_0(w,z))+(d_0(z,w)+d_0(w,y))\ge d_0(x,w)+d_0(w,y)\ge d_0(x,y)$, with equality only if $z=w$ (which is a point of $Z_1$) and $d_0(x,w)+d_0(w,y)=d_0(x,y)$; thus $I(x,y)$ is computed in $Z_1$, where the induction hypothesis applies. Step, case $x,y\in {\iota }_e(C_e)$: for $z\in {\iota }_e(C_e)$ the sum is $\mathrm{\mid }{t}_x-t_z\mathrm{\mid }+\mathrm{\mid }{t}_z-t_y\mathrm{\mid }$, equal to $\mathrm{\mid }{t}_x-t_y\mathrm{\mid }$ exactly for $t_z$ between $t_x$ and $t_y$ [F4]; for $z\in Z_1$ with $z\mathrm{\ne }w$ the sum is $(d_0(x,w)+d_0(w,z))+(d_0(w,z)+d_0(w,y))>d_0(x,w)+d_0(w,y)\ge \mathrm{\mid }{t}_x-t_y\mathrm{\mid }$ by step 2.1; and $z=w$ is a point of ${\iota }_e(C_e)$ with coordinate ${\mathrm{\ell }}_e$. Hence $I(x,y)$ is the set of points of ${\iota }_e(C_e)$ whose coordinate lies between $t_x$ and $t_y$, on which $z\mapsto d_0(x,z)=\mathrm{\mid }{t}_x-t_z\mathrm{\mid }$ is injective. Step, case $x\in {\iota }_e(C_e)$, $y\in Z_1$: for $z\in {\iota }_e(C_e)$ the sum is $d_0(x,z)+d_0(z,w)+d_0(w,y)\ge d_0(x,w)+d_0(w,y)=d_0(x,y)$, with equality exactly when $d_0(x,z)+d_0(z,w)=d_0(x,w)$, that is, when $t_z$ lies between $t_x$ and ${\mathrm{\ell }}_e$; for $z\in Z_1$ the sum is $d_0(x,w)+d_0(w,z)+d_0(z,y)$, equal to $d_0(x,y)$ exactly when $d_0(w,z)+d_0(z,y)=d_0(w,y)$, that is, when $z\in I_{Z_1}(w,y)$. On the first part $z\mapsto d_0(x,z)=\mathrm{\mid }{t}_x-t_z\mathrm{\mid }$ is injective, on the second it is $d_0(x,w)+d_0(w,z)$, injective by the induction hypothesis, the distance values on the first part lie in $[0,d_0(x,w)]$ and those on the second lie in $[d_0(x,w),d_0(x,y)]$, with the shared boundary value attained only at $w$. Thus injectivity holds across the two parts as well. For the opposite ordering $x\in Z_1$, $y\in {\iota }_e(C_e)$, apply this case to $I(y,x)=I(x,y)$: injectivity of $z\mapsto d_0(y,z)$ and the identity $d_0(x,z)=d_0(x,y)-d_0(y,z)$ on $I(x,y)$ give injectivity from $x$ as well. Consequently, if $\gamma$ is a geodesic segment from $x$ to $y$ with $R=d_0(x,y)$, then for every $s$ the point $\gamma (s)$ satisfies $d_0(x,\gamma (s))+d_0(\gamma (s),y)=s+(R-s)=R$, so $\gamma (s)\in I(x,y)$ and $d_0(x,\gamma (s))=s$; injectivity of $z\mapsto d_0(x,z)$ on $I(x,y)$ determines $\gamma (s)$ uniquely for every $s$. Hence the geodesic segment is unique, proving (c); existence follows recursively: use the straight unit-speed interval segment for two points in the leaf interval, the inductively supplied geodesic for two points in $Z_1$, and their concatenation at $w$ for the cross case. Step 2.1 gives the isometry equality also for parameter pairs on opposite sides of $w$; when $x=y$ use the constant map on $[0,0]$.

(Application to $\mathrm{\Gamma }$.) Steps 1.2, 2.1 and 3.1 apply to the finite tree $\mathrm{\Gamma }$ with its edge lengths; in the unit case ${\mathrm{\ell }}_e=1$ all cells are intervals of length $1$, so there are two shapes (points and unit intervals), and the recursively defined $\lambda$ is the length of the tree path.

(Clause (i).) Let $v,w\in V$. By clause (b) of the induction claim, $d(v,w)$ is the sum of the edge lengths over the unique reduced path of $\mathrm{\Gamma }$ from $v$ to $w$, which for ${\mathrm{\ell }}_e=1$ all is the number of its edges; by [F5] the graph path metric $d_{\mathrm{\Gamma }}(v,w)$ is the least length of a path joining $v$ and $w$, and by the uniqueness of the reduced path in a tree the only reduced walk is that path, so $d_{\mathrm{\Gamma }}(v,w)$ is the same number. Hence $d(v,w)=d_{\mathrm{\Gamma }}(v,w)$ on $V$.

(Clause (ii).) Existence and uniqueness of the geodesic segment joining any two points of $X_{\mathrm{\Gamma }}$ are clauses (c) of the induction claim, verified in steps 1.2 and 3.1. For an edge $e$ and $u$ an endpoint of $e$, the midpoint $m$ of $e$ is the point of ${\iota }_e(C_e)$ at coordinate ${\mathrm{\ell }}_e\mathrm{/}2$, so $d(m,u)=\mathrm{\mid }{\mathrm{\ell }}_e\mathrm{/}2-0\mathrm{\mid }={\mathrm{\ell }}_e\mathrm{/}2$ by the same-cell case of step 2.1, which in the unit case is $1\mathrm{/}2$; in particular $d$ takes the non-integer value $1\mathrm{/}2$ between two points of $X_{\mathrm{\Gamma }}$, while the graph metric takes only integer values on distinct vertices by clause (i).

(Clause (iii).) If $\mathrm{\Gamma }$ has an edge, let $v,w$ be its endpoints; by clause (i) and [F5], $d_{\mathrm{\Gamma }}(v,w)=d(v,w)=1$. If the metric space $(V,d_{\mathrm{\Gamma }})$ were geodesic, a geodesic segment from $v$ to $w$ would have length $1$ and its point at parameter $1\mathrm{/}2$ would satisfy $d_{\mathrm{\Gamma }}(v,p)=d_{\mathrm{\Gamma }}(p,w)=1\mathrm{/}2$ [F3]; but on the vertex set $d_{\mathrm{\Gamma }}$ counts edges of paths [F5], so all its nonzero values are at least $1$ and $1\mathrm{/}2$ is impossible. Hence $(V,d_{\mathrm{\Gamma }})$ is not geodesic when $\mathrm{\Gamma }$ has an edge.

(Clause (iv).) The general positive edge lengths were carried through steps 1.2, 2.1, 3.1 and 4.1 without change, so by clause (b) $d(v,w)={\sum }_{e\in \mathrm{path}(v,w)}{\mathrm{\ell }}_e$ on vertices. If some ${\mathrm{\ell }}_{e_0}\mathrm{\ne }1$, then for the two endpoints $v,w$ of $e_0$ one has $d(v,w)={\mathrm{\ell }}_{e_0}\mathrm{\ne }1=d_{\mathrm{\Gamma }}(v,w)$, so the weighted path length and the unweighted graph distance differ; conversely, if every ${\mathrm{\ell }}_e=1$ they agree by clause (i). For the single edge of length $2$ the two values are $d(v,w)=2$ and $d_{\mathrm{\Gamma }}(v,w)=1$.