Path in Tree is Unique

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $T$ be a graph.


Then $T$ is a tree if and only if there is exactly one path between any two vertices.


Proof

Necessary Condition

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.

$\Box$


Sufficient Condition

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)$.

Hence, by Modus Tollendo Tollens, $T$ can have no circuits.

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

$\blacksquare$