Path in Tree is Unique

From ProofWiki
Jump to navigation Jump to search


Let $T$ be a graph.

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


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.


Sufficient Condition

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

Then a priori $T$ is connected.

Suppose $T$ had a circuit, say $\tuple {u, u_1, u_2, \ldots, u_n, v, u}$.

Then there are two paths from $u$ to $v$:

$\tuple {u, u_1, u_2, \ldots, u_n, v}$


$\tuple {u, v}$

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

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