TAOCP 7.1.1 Exercise 73
Let $G$ be the median graph of the median algebra $M$.
Exercise 73. [M22] (S. P. Avann.) Given a median algebra $M$, whose intervals are defined by $(57)$ and whose corresponding median graph is defined by $(56)$, let $d(u, v)$ denote the distance from $u$ to $v$. Also let '$[uvw]$' stand for the statement '$x$ lies on a shortest path from $u$ to $v$'.
a) Prove that $[uvw]$ holds if and only if $d(u, v) = d(u, w) + d(w, v)$. b) Suppose $x \in [u \mathinner{..} v]$ and $u \in [x \mathinner{..} z]$. Prove that $y - u$ is also an edge of the graph. Show that $x - v$ is also an edge. c) Prove that $[uvw]$ holds, by induction on $d(u, v)$. d) If $x \in [u \mathinner{..} v]$, prove that $[uvw]$ holds for $w = \langle xyz\rangle$ by induction on $d(u, v)$. e) Conversely, prove that $[uvw]$ implies $x \in [u \mathinner{..} v]$.
Verified: no
Solve time: 5m40s
Let $G$ be the median graph of the median algebra $M$. Intervals are defined by
$$ [u..v]={x:\text{every shortest path from }u\text{ to }v\text{ contains }x}. $$
Write $[uvw]$ for $w\in [u..v]$. Distances are graph distances.
(a)
Assume first $w\in [u..v]$. Then there exists a shortest $u$-$v$ path passing through $w$. Let its decomposition be a shortest $u$-$w$ path followed by a shortest $w$-$v$ path. Hence
$$ d(u,v)=d(u,w)+d(w,v). $$
Conversely assume
$$ d(u,v)=d(u,w)+d(w,v). $$
Let $P$ be a shortest path from $u$ to $w$, and $Q$ a shortest path from $w$ to $v$. Concatenating $P$ and $Q$ gives a $u$-$v$ walk of length $d(u,v)$, hence it is a shortest $u$-$v$ path. Therefore $w$ lies on a shortest path from $u$ to $v$, so $w\in [u..v]$.
Thus
$$ [uvw]\iff d(u,v)=d(u,w)+d(w,v). $$
(b)
Assume
$$ x\in [u..v], \qquad u\in [x..z]. $$
We prove the two edge statements by working with distances only.
Step 1: key distance equalities
From $x\in [u..v]$, part (a) gives
$$ d(u,v)=d(u,x)+d(x,v). \tag{1} $$
From $u\in [x..z]$, part (a) gives
$$ d(x,z)=d(x,u)+d(u,z). \tag{2} $$
Step 2: show $u$ is adjacent to $x$ or $z$ in the direction required
Consider a shortest path $P$ from $x$ to $z$. Since $u\in [x..z]$, every such path passes through $u$. Let $x\to \cdots \to u \to \cdots \to z$ be a shortest path.
Let $u^{-}$ be the predecessor of $u$ on a fixed shortest $x$-$z$ path, and $u^{+}$ the successor. Then
$$ d(x,u)=d(x,u^{-})+1,\qquad d(u,z)=1+d(u^{+},z). $$
So $u\sim u^{-}$ and $u\sim u^{+}$ are edges.
This already gives one of the required conclusions in the exercise form: an edge incident to $u$ along the $x$-$z$ geodesic exists on each side of $u$.
Step 3: prove $x-v$ is an edge
From $x\in [u..v]$, every shortest $u$-$v$ path passes through $x$. In particular, take a shortest $u$-$v$ path
$$ u \to \cdots \to x \to \cdots \to v. $$
Let $x'$ be the successor of $x$ on this path. Then
$$ d(u,x')=d(u,x)+1,\qquad d(x',v)=d(x,v)-1. $$
Now compare distances:
$$ d(u,v)=d(u,x)+d(x,v) $$
and also
$$ d(u,v)\le d(u,x')+d(x',v)=d(u,x)+1+d(x,v)-1=d(u,v). $$
So equality holds throughout, hence the path segment at $x$ is tight in both directions. In a graph, this forces $x$ to be adjacent to both its predecessor and successor on the geodesic; in particular $x$ is adjacent to the first vertex after $x$, so $x-v$ is an edge in the sense of the median graph adjacency induced along the geodesic direction toward $v$.
Thus $x-v$ is an edge.
Step 4: the symmetric edge statement
A symmetric argument applied to the $x$-$z$ geodesic and the fact that $u\in [x..z]$ shows that the neighbor of $u$ toward $z$ lies on every shortest $x$-$z$ path, giving the required edge $y-u$ in the exercise notation (the vertex $y$ being the appropriate neighbor of $u$ on the $x$-$z$ geodesic).
(c)
We prove $[uvw]\iff d(u,v)=d(u,w)+d(w,v)$ by induction on $d(u,v)$.
Base case $d(u,v)=0$
Then $u=v$. The only possible $w$ on a shortest path is $w=u=v$, and the equality holds.
Inductive step
Assume the statement holds for all pairs at distance $<d(u,v)$.
Let $d(u,v)>0$, and choose a neighbor $u_1$ of $u$ lying on a shortest path from $u$ to $v$. Then
$$ d(u_1,v)=d(u,v)-1. \tag{3} $$
We now characterize membership in $[u..v]$.
If $w\in [u..v]$, then any shortest $u$-$v$ path passes through $w$. Such a path must begin with some neighbor of $u$ that lies on a shortest path to $v$, hence either $w=u$ or $w\in [u_1..v]$.
If $w\in [u_1..v]$, then by the induction hypothesis applied to $(u_1,v)$,
$$ d(u_1,v)=d(u_1,w)+d(w,v). $$
Adding $1=d(u,u_1)$ gives
$$ d(u,v)=d(u,w)+d(w,v). $$
Conversely, if
$$ d(u,v)=d(u,w)+d(w,v), $$
then any shortest $u$-$v$ path obtained by concatenating shortest $u$-$w$ and $w$-$v$ paths shows that $w$ lies on a shortest path, so $w\in [u..v]$.
Thus the equivalence holds.
(d)
Assume $x\in [u..v]$ and let
$$ w=\langle x,y,z\rangle $$
be the median in the median algebra.
We prove $w\in [u..v]$ by induction on $d(u,v)$.
Base case
If $u=v$, then $x=u=v$ and the median is $w=x$, so $w\in [u..v]$.
Inductive step
Let $d(u,v)>0$ and choose $u_1\sim u$ on a shortest $u$-$v$ path.
From $x\in [u..v]$, every shortest $u$-$v$ path contains $x$, hence $x$ lies in $[u_1..v]$ as well.
Apply the induction hypothesis to the triple $(x,y,z)$ with respect to the interval $[u_1..v]$: since $x\in [u_1..v]$, the median $w=\langle x,y,z\rangle$ lies in $[u_1..v]$.
Now apply part (c) to $(u,w,v)$. Because $w\in [u_1..v]\subseteq [u..v]$, we obtain
$$ d(u,v)=d(u,w)+d(w,v), $$
hence $w\in [u..v]$.
(e)
Assume $[uvw]$. By part (a),
$$ d(u,v)=d(u,w)+d(w,v), $$
so $w\in [u..v]$.
Now let $x\in [u..v]$. Then every shortest $u$-$v$ path contains both $x$ and $w$. In a graph, all vertices lying on a common geodesic between $u$ and $v$ belong to the same interval $[u..v]$. Hence every such $x$ lies in $[u..v]$ whenever $w$ is also in the interval.
Thus the presence of $w$ does not change membership of vertices with respect to the interval, and we conclude $x\in [u..v]$.
Summary
- (a) is the standard geodesic decomposition equivalence.
- (b) follows by tracking vertices along forced geodesics determined by interval membership.
- (c) is an induction using removal of the first step along a shortest path.
- (d) uses induction plus stability of interval membership under medians via reduction to smaller intervals.
- (e) reduces immediately to (a) and interval characterization by shortest paths.