Paths in Trees are Unique

From ProofWiki

Jump to: navigation, search

Theorem

Let $T$ be a graph.

Then $T$ is a tree iff there is exactly one path between any two vertices.

Suppose $T$ is a tree.

As a tree is by definition connected, there exists at least one path between each pair of vertices.

Suppose there is more than one path between two vertices $u, v \in T$.

Let two of these paths be:

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

Now consider the path $P_3 = \left({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}\right)$.

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

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

$\Box$

Let $T$ be such that between any two vertices there is exactly one path.

Then for a start $T$ is by definition connected.

Suppose $T$ had a circuit, say $\left({u, u_1, u_2, \ldots, u_n, v, u}\right)$.

Then there are two paths from $u$ to $v$: $\left({u, u_1, u_2, \ldots, u_n, v}\right)$ and $\left({u, v}\right)$.

That is, by definition, $T$ is a tree.

$\blacksquare$