Branch of Finite Tree is Finite

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $T$ be a finite rooted tree with root node $r_T$.

Let $\Gamma$ be a branch of $T$.


Then $\Gamma$ is a finite branch.


Proof

Let $\Gamma$ be a branch of a finite rooted tree $T$.

Aiming for a contradiction, suppose $\Gamma$ were an infinite branch of $T$.

By definition $\Gamma$ contains an infinite number of nodes.



From Subset of Finite Set is Finite, it follows that $\Gamma$ has a finite number of nodes.

From this contradiction it follows that $\Gamma$ can not be an infinite branch of $T$.

Hence the result.

$\blacksquare$


Sources