TAOCP 7.1.1 Exercise 93
Let $X$ be a retract of a graph $G$.
Exercise 93. [M20] [M20] Prove that every retract $X$ of a graph $G$ is an isometric subgraph of $G$. (In other words, distances in $X$ are the same as in $G$; see exercise 80.)
Verified: yes
Solve time: 2m14s
Let $X$ be a retract of a graph $G$. Thus there exists a retraction $r:V(G)\to V(X)$ such that $r(x)=x$ for all $x\in V(X)$, and for every edge $(u,v)$ of $G$, either $r(u)=r(v)$ or $(r(u),r(v))$ is an edge of $X$.
Let $u,v\in V(X)$. Write distances in $G$ and $X$ as $d_G$ and $d_X$.
1. First inequality: $d_G(u,v)\le d_X(u,v)$
Every path in $X$ is also a path in $G$, since $X$ is a subgraph of $G$. Therefore every $u$-$v$ path in $X$ is a $u$-$v$ path in $G$, so the shortest path in $G$ cannot be longer than the shortest path in $X$. Hence
$$ d_G(u,v)\le d_X(u,v). $$
2. Second inequality: $d_X(u,v)\le d_G(u,v)$
Let
$$ P: u=x_0,x_1,\dots,x_k=v $$
be a shortest path in $G$, so $k=d_G(u,v)$.
Apply $r$ to obtain the sequence
$$ r(x_0),r(x_1),\dots,r(x_k). $$
Since each $(x_i,x_{i+1})$ is an edge of $G$, the defining property of a retraction implies that either $r(x_i)=r(x_{i+1})$ or $(r(x_i),r(x_{i+1}))$ is an edge of $X$. Thus this sequence is a walk in $X$ from $u$ to $v$ of length at most $k$, after deleting trivial steps where consecutive vertices coincide.
So we obtain a $u$-$v$ walk in $X$ of length $\le k$.
We now use the standard fact:
Lemma. Every $u$-$v$ walk in a graph contains a $u$-$v$ path whose length is at most the length of the walk.
Proof of lemma. Among all $u$-$v$ subwalks of the given walk, choose one with minimum length. If this subwalk repeats a vertex, then it contains a cycle. Removing the cycle produces a strictly shorter $u$-$v$ subwalk, contradicting minimality. Hence the minimal subwalk has no repeated vertices and is a simple path. Its length is at most the original walk length. ∎
Applying the lemma to the walk in $X$, we obtain a $u$-$v$ path in $X$ of length at most $k$. Therefore
$$ d_X(u,v)\le k = d_G(u,v). $$
3. Conclusion
Combining both inequalities,
$$ d_G(u,v)\le d_X(u,v)\le d_G(u,v), $$
so
$$ d_X(u,v)=d_G(u,v) $$
for all $u,v\in V(X)$. Hence $X$ is an isometric subgraph of $G$. ∎