Let $G = (V,E)$ be a tree with at least $2$ vertices. Show that for every $u,v$ $\epsilon V$, there exists a unique path from $u$ to $v$.
My attempt:
Suppose for contradiction, there are $2$ distinct paths from $u$ to $v$
$v = p_{1}, p_{2}, ......, p_{k} = v$
$v = q_{1}, q_{2}, ......, q_{k} = v$
How do I prove that there is a cycle formed through this contradiction?
Let there be two paths, $v_1,v_2,\ldots, v_k$ and $w_1,w_2,\ldots,w_\ell$, both of which start at $a$ and end at $b$ and such that for all $i,j$ we have $c_i\neq w_j$. That is, they share no vertices in common. Then the following path is a cycle:
$$a,v_1,\ldots,v_k,b,w_\ell,\ldots,w_1$$
The key idea is that if you go from $a$ to $b$ along one path, then you can go back the other way from $b$ to $a$.
However, this alone is not a proof. For a contradiction, we are assuming that there exists an $a$ and a $b$ such that there are two paths that are not identical. However, "not identical" only requires one vertex to be different, while our argument requires that every vertex be different. What we need to show now is that if there is some path that differs somewhere, then there exist two other vertices $a',b'$ such that $a',b'$ have two entirely disjoint paths between them.
Luckily (as per the excellent comment) there's an easy way to handle this issue: consider the minimal example. Let $S$ be the set of all pairs of vertices with two paths, and take the one that has the shortest sum of path lengths. This will be an example where the paths are entirely disjoint, because if the lists were $a,v_1,\ldots, v_k,b$ and $a,v_1,w_2,\ldots,w_\ell,b$ then $(v_1,b)$ would have a shorter total path length than $(a,b)$!
One you've done the above, you've proven that if there's a path between $a$ and $b$ then it's unique. However, we also need to show that there is a path between $a$ and $b$. This bit is easy, but depends on your definitions. Prove that there is a path from every vertex to the root of the tree, and then just take the union of the paths from $a$ to the root and the path from $b$ to the root. A subset of this will be a path from $a$ to $b$ (can you give an algorithm that tells you which subset?)