Equivalent Definitions for Finite Tree

This page has been identified as a candidate for refactoring of medium complexity. In particular: Extract all these definitions into subdefinition pages for Finite Tree and/or a Characterizations result Until this has been finished, please leave {{Refactor}} in the code. New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Refactor}} from the code.

Theorem

Let $T$ be a finite tree of order $n$.

The following statements are equivalent:

$(1): \quad T$ is connected and has no circuits.

$(2): \quad T$ has $n-1$ edges and has no circuits.

$(3): \quad T$ is connected and has $n-1$ edges.

$(4): \quad$ Any two vertices of $T$ are connected by exactly one path.

$(5): \quad T$ has no circuits, but adding one edge creates a cycle.

Proof

Statement $1$ is the usual definition of a tree.

1 implies 2

• The fact that $T$ has no circuits is part of statement $1$.

• The fact that $T$ has $n-1$ edges is proved in Finite Connected Graph is Tree iff Size is One Less than Order.

$\Box$

2 implies 3

• The fact that $T$ has $n-1$ edges is part of statement $2$.

• The fact that $T$ is connected is proved in Finite Connected Graph is Tree iff Size is One Less than Order.

$\Box$

3 implies 1

• The fact that $T$ is connected is part of statement $3$.

• Given that $T$ has $n-1$ edges, the fact that it has no circuits is proved during the course of the proof of Finite Connected Graph is Tree iff Size is One Less than Order.

$\Box$

1 implies and is implied by 4

This is proved by Path in Tree is Unique.

$\Box$

1 implies 5

Suppose $T = \struct {V, E}$ is connected and has no circuits.

Let $u, v \in V$ be any two vertices of $T$.

Let $P = \tuple {u, u_1, u_2, \ldots, u_{n - 1}, v}$ be a path from $u$ to $v$.

Let a new edges $\set {u, v}$ be added.

Then $\tuple {u, u_1, u_2, \ldots, u_{n - 1}, v, u}$ is now a cycle, which is by definition also a circuit, in $T$.

Note that this applies even when $P = \tuple {u, v}$: $\tuple {u, v, u}$ is still a cycle in $T$, but now $T$ is a multigraph.

$\Box$

5 implies 1

Suppose $T$ has no circuits, but adding one edge creates a cycle, which is by definition also a circuit.

If $T$ were disconnected, then it would be possible to add an edge $e$ to connect two components of $T$.

By definition, $e$ would be a bridge.

From Condition for Edge to be Bridge, it follows that $e$ does not lie on a circuit.

So, if the only way to add an edge to $T$ forms a cycle, it follows that $T$ must be connected.

So $T$ is connected and has no circuits.

$\Box$

Thus, all the above can be used as a definition for a finite tree.

$\blacksquare$