# Equivalent Definitions for Finite Tree

## Contents

## Theorem

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

The following statements are equivalent:

- $(4): \quad T$ is connected, and the removal of any one edge renders $T$ disconnected.

## 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 Size of Tree 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 Size of Tree 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 Size of Tree is One Less than Order.

$\Box$

### 1 implies 4

As $T$ has no circuits, then from Condition for Edge to be Bridge, every edge is a bridge.

Thus removing any edge of $T$ will disconnect $T$.

$\Box$

### 4 implies 1

If by removing any one edge between two vertices of $T$ renders it disconnected, then that means each edge must be a bridge.

So by Condition for Edge to be Bridge, $T$ has no circuits.

$\Box$

### 1 implies and is implied by 5

This is proved by Path in Tree is Unique.

$\Box$

### 1 implies 6

Suppose $T = \left({V, E}\right)$ is connected and has no circuits.

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

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

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

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

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

$\Box$

### 6 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$