Trees

Characteristics of a tree

A tree is a connected graph that has no cycles. The graph below is an example of a tree since it’s connected and does not contain a cycle.

Path graphs are also examples of trees. In the context of trees, an isolated vertex (the trivial path) is called the trivial tree.

A vertex in a tree that has degree $1$ is called a leaf of that tree. All other vertices having a degree of at least $2$ are called internal nodes. For example, the tree shown above has $5$ leaves and $3$ ...