Session 03 - Introduction to Graph Theory III

#math

Introduction To Trees

Definition

A tree is connected undirected graph with no simple circuits.

Theorem

An undirected graph is a tree if and only if there is a unique simple path between any two of its vertices.

Proof

$(\Rightarrow)$
Since the graph is a tree there are no cycles therefore any path is unique.
( $\Leftarrow$ )
Assume that for any pair vertices, $v, u \in V$ , there is unique path, we shall prove that there are no cycles by assuming the graph does contain a cycle $c_{0} c_{1} . . . c_{n}$ then notice that one can form a path from $c_{0}$ to $c_{n}$ by taking two distinct paths $c_{0} c_{2} . . . c_{n}$ or $c_{0} c_{n}$ . Thus the path is not unique contradicting our assumption.

Definition

A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.

Definition

A rooted tree is called an $m$ -ary tree if every interal vertex has no more than $m$ children.
The tree is called a full $m$ -ary tree if every internal vertex has exactly $m$ children.
An $m$ -ary for $m = 2$ is called a binary tree.

Definition

An ordered rooted tree is a rooted tree where the children of each internal vertex are ordered.

Theorem

A tree with $n$ vertices has $n - 1$ edges

Proof

By induction on $n$ .

Theorem

A full m-ary tree with $i$ internal vertices contains $n = m i + 1$ vertices.

Proof

Every vertex must be a child of a unique internal vertex except for the root. $◻$

Definition

The level of a vertex in a rooted tree is the length of the unique path from the root to the vertex.
The level of the root is defined to be $0.$

Definition

The height of a tree is the maximum level of a tree.

Definition

A tree of height $h$ is balanced if all its leaves are either at level $h$ or $h - 1$ .