Proof of unique paths in trees

Proof

We prove both directions. Step 1 is a fact about closed walks that both directions use.

1. Let $(z_0, z_1, \dots, z_m)$ be a closed walk with $m \ge 3$, $z_m = z_0$, and $z_1, \dots, z_m$ pairwise distinct. Then its $m$ edges are pairwise distinct, so it is a circuit, and hence a cycle.
2. Proof of step 1. Read the indices modulo $m$. The edges are $\set{z_{t-1}, z_t}$ for $t = 1, \dots, m$. Two of them can be equal only if the pairs share both vertices.
3. Since $z_1, \dots, z_m$ are distinct, the equality $\set{z_{s-1}, z_s} = \set{z_{t-1}, z_t}$ with $s \ne t$ forces $z_{s-1} = z_t$ and $z_s = z_{t-1}$. Then $t \equiv s - 1$ and $s \equiv t - 1$, so $2 \equiv 0$ modulo $m$, which is false for $m \ge 3$.
4. ($\Rightarrow$) Let $G$ be a tree. It is connected, so it has a vertex and any two vertices $u, v$ are joined by a walk.
5. By every walk contains a path, there is a path from $u$ to $v$.
6. Suppose $P = (p_0, \dots, p_a)$ and $Q = (q_0, \dots, q_b)$ are different paths from $u$ to $v$.
7. Neither is a proper initial part of the other. For example, if $a < b$ and $p_t = q_t$ for $t \le a$, then $q_a = p_a = v = q_b$, which contradicts the distinct vertices of $Q$.
8. So there is a least index $i$ with $1 \le i \le \min(a, b)$ and $p_i \ne q_i$. Then $p_{i-1} = q_{i-1}$; call this vertex $x$.
9. Let $j \ge i$ be the least index such that $p_j = q_l$ for some $l \ge i$. It exists, because $p_a = v = q_b$ and $b \ge i$.
10. Consider the closed walk $C = (x, p_i, p_{i+1}, \dots, p_j, q_{l-1}, q_{l-2}, \dots, q_i, x)$, where $p_j = q_l$ and $q_{i-1} = x$. Its length is $(j - i + 1) + (l - i + 1)$.
11. The vertices $p_i, \dots, p_j$ are distinct and differ from $x = p_{i-1}$, since $P$ is a path. The vertices $q_{l-1}, \dots, q_i$ are distinct and differ from $x = q_{i-1}$, since $Q$ is a path.
12. No $q_t$ with $i \le t < l$ equals some $p_s$ with $i \le s \le j$. For $s < j$ this follows from the minimality of $j$, and for $s = j$ from $p_j = q_l$ and $t \ne l$.
13. So the vertices of $C$ after the first are pairwise distinct. If the length were $2$, then $j = l = i$ and $p_i = q_i$, which is false. So the length is at least $3$.
14. By step 1, $C$ is a cycle in $G$. This contradicts that $G$ is acyclic. Hence the path from $u$ to $v$ is unique.
15. ($\Leftarrow$) Suppose $G$ has a vertex, and any two vertices are joined by exactly one path.
16. A path is a walk, so any two vertices are reachable from each other. So $G$ is connected.
17. Suppose $G$ has a cycle $(w_0, w_1, \dots, w_k)$. Its length $k$ is at least $3$: $k = 1$ needs a loop, and $k = 2$ uses the edge $w_0 w_1$ twice.
18. Then $(w_0, w_1)$ and $(w_k, w_{k-1}, \dots, w_1)$ are paths from $w_0 = w_k$ to $w_1$. The second has distinct vertices because $w_1, \dots, w_k$ are distinct.
19. These two paths have lengths $1$ and $k - 1 \ge 2$, so they are different. This contradicts uniqueness, so $G$ is acyclic.
20. By steps 16 and 19, $G$ is a tree.