TAOCP 7.1.1 Exercise 78
Let $G$ be a median graph and fix the root $a$.
Exercise 78. ▶ [M36] If the vertex $v$ is examined $k$ times in step I4 during the execution of Algorithm I, prove that the graph has at least $2^k$ vertices. Hint: There are $k$ ways to start a shortest path from $v$ to $a$; thus at least $k$ lie in $l(v)$.
Verified: no
Solve time: 3m50s
Let $G$ be a median graph and fix the root $a$. Let Algorithm I be executed and suppose the vertex $v$ is examined $k$ times in step I4.
1. Each examination determines a shortest-path first step
Each time $v$ is examined in step I4, the algorithm chooses a shortest path from $v$ to $a$, hence it chooses the first edge of such a path. Let these first steps be edges
$$ v u_1,\dots, v u_k. $$
We first show that these neighbors are all distinct.
If two examinations produced the same neighbor $u$, then the corresponding shortest $v$-to-$a$ paths would begin with the same edge $vu$. In a median graph (indeed, in any graph), once the first step is fixed, Algorithm I performs identical deterministic work in the local structure around $u$, so the examination would not produce a genuinely new shortest-path choice. Hence distinct examinations must yield distinct neighbors $u_i$.
Thus $v$ has at least $k$ distinct neighbors $u_1,\dots,u_k$, each lying on some shortest path from $v$ to $a$.
2. Distinct neighbors correspond to distinct $\Theta$-classes
In a median graph, every $\Theta$-class is a matching: no two edges in the same $\Theta$-class share a common endpoint. Therefore, at a fixed vertex $v$, there is at most one edge incident with $v$ from any given $\Theta$-class.
Since the edges $v u_i$ are all distinct and incident with $v$, they must belong to distinct $\Theta$-classes. Denote these classes by
$$ \Theta_1,\dots,\Theta_k. $$
Each $\Theta_i$ contains the edge $v u_i$ and hence separates $v$ from $a$, because $v u_i$ lies on a shortest $v$-to-$a$ path.
3. Embedding into a hypercube via $\Theta$-classes
A fundamental property of median graphs is that they are partial cubes: there exists an isometric embedding
$$ \varphi: V(G)\to {0,1}^m $$
such that each $\Theta$-class corresponds to one coordinate, and graph distance equals Hamming distance.
Under this representation:
- each $\Theta$-class $\Theta_i$ corresponds to a coordinate function $\varphi_i$,
- removing $\Theta_i$ splits $V(G)$ into two convex halfspaces, given by $\varphi_i=0$ and $\varphi_i=1$,
- along any shortest path, each $\Theta$-class is crossed at most once.
Let $d(v,a)$ be the number of $\Theta$-classes separating $v$ and $a$. Then the interval $I(v,a)$ consists exactly of those vertices whose coordinates agree with $v$ or $a$ in each separating coordinate, and it is isomorphic to a $d(v,a)$-dimensional subcube. Hence
$$ |I(v,a)| = 2^{d(v,a)}. $$
4. The $k$ classes occur among the separating coordinates
Each $\Theta_i$ lies on a shortest path from $v$ to $a$, so each $\Theta_i$ is one of the $\Theta$-classes that separate $v$ and $a$. Therefore
$$ k \le d(v,a). $$
5. Counting vertices in the interval
Since $I(v,a)$ is a $d(v,a)$-dimensional cube in the partial cube representation, it contains exactly $2^{d(v,a)}$ vertices. Therefore,
$$ |I(v,a)| = 2^{d(v,a)} \ge 2^k. $$
Finally, $I(v,a)\subseteq V(G)$, so
$$ |V(G)| \ge 2^k. $$
Conclusion
If $v$ is examined $k$ times in step I4 of Algorithm I, then $v$ is incident with $k$ distinct $\Theta$-classes separating $v$ from $a$, implying that $d(v,a)\ge k$. Since the interval $I(v,a)$ is a $d(v,a)$-dimensional hypercube in any median graph,
$$ |V(G)| \ge |I(v,a)| = 2^{d(v,a)} \ge 2^k. $$
$$ \boxed{|V(G)| \ge 2^k.} $$