Graph theory, unique path of tree proof 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?
 A: 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?)
A: Assume graph $T$ is a tree. Let $u$ and $v$ be distinct vertices in that assumed tree. If $T$ has one vertex, then the conclusion is satisfied automatically as there is only one path to get to one vertex.
Now we must show the following:

*

*There is a path.

*There is not more than one path connecting to vertices.

The first part is satisfied by our assumption that $T$ is a tree. Recall that trees are acyclic connected graphs. Check ✔️.
Next, to prove that the path is unique, we're going do something counterintuitive: we're going to imagine the exact opposite of a unique path, that is, we're going to imagine a tree with two paths between $u$ and $v$. A path's uniqueness is determined by what was previously mentioned: "There is not more than one path connecting to vertices." Now have two paths connecting the same vertices.
If our tree has two paths connecting $u$ to $v$, we know that these paths must start the same way and differ somewhere along the way. Because these paths go to the same end, the paths must converge at the same vertex.
In fact, they must diverge at a common vertex $u'$ and converge at a common vertex $v'$. Look what that gives us:
   u
   u'
  / \
 x   y
  \ /
   v'
   v

Another image of a cyclic graph
We arrived at a contradiction regarding the "acyclic" property of trees. Trees are "acyclic connected graphs." What we have shown above is a cyclic connected graph, not a tree.
