Proof.

This is an “if and only if” statement, so we must prove two implications. We start by proving that if \(T\) is a tree, then between every pair of distinct vertices there is a unique path.

Assume \(T\) is a tree, and let \(u\) and \(v\) be distinct vertices (if \(T\) only has one vertex, then the conclusion is satisfied automatically). We must show two things to show that there is a unique path between \(u\) and \(v\text{:}\) that there is a path, and that there is not more than one path. The first of these is automatic, since \(T\) is a tree, it is connected, so there is a path between any pair of vertices.

To show the path is unique, we suppose there are two paths between \(u\) and \(v\text{,}\) and get a contradiction. The two paths might start out the same, but since they are different, there is some first vertex \(u'\) after which the two paths diverge. However, since the two paths both end and \(v\text{,}\) there is some first vertex after \(u'\) that they have in common, call it \(v'\text{.}\) Now consider the two paths from \(u'\) to \(v'\text{.}\) Taken together, these form a cycle, which contradicts our assumption that \(T\) is a tree.

Now we consider the converse: if between every pair of distinct vertices of \(T\) there is a unique path, then \(T\) is a tree. So assume the hypothesis: between every pair of distinct vertices of \(T\) there is a unique path. To prove that \(T\) is a tree, we must show it is connected and contains no cycles.

The first half of this is easy: \(T\) is connected, because there is a path between every pair of vertices. To show that \(T\) has no cycles, we assume it does, for the sake of contradiction. Let \(u\) and \(v\) be two distinct vertices in a cycle of \(T\text{.}\) Since we can get from \(u\) to \(v\) by going clockwise or counterclockwise around the cycle, there are two paths from \(u\) and \(v\text{,}\) contradicting our assumption.

We have established both directions so we have completed the proof.