Path in Tree is Unique/Necessary Condition

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $T$ be a tree.

Then there is exactly one path between any two vertices.


Proof

Let $T$ be a tree.

Aiming for a contradiction, suppose there exists a pair of vertices $u$ and $v$ in $T$ such that there is not exactly one path between them.

If there is no path between $u$ and $v$, $T$ is not connected.

In this case, $T$ is certainly not a tree.

So, in keeping with our supposition, there is more than one path between $u$ and $v$.

Let two of these paths be:

$P_1 = \tuple {u, u_1, \ldots, u_i, r_1, r_2, \ldots, r_{j - 1}, r_j, u_{i + 1}, \ldots, v}$
$P_2 = \tuple {u, u_1, \ldots, u_i, s_1, s_2, \ldots, s_{k - 1}, s_k, u_{i + 1}, \ldots, v}$

Now consider the path:

$P_3 = \tuple {u_i, r_1, r_2, \ldots, r_{j - 1}, r_j, u_{i + 1}, s_k, s_{k - 1}, \ldots, s_2, s_1, u_i}$

It can be seen that $P_3$ is a circuit.

Thus by definition $T$ can not be a tree.

From Proof by Contradiction it follows that there is exactly one path between any pair of vertices.

$\blacksquare$


Sources