Tree

Topics: Graph Theory

---

(definition)

A tree is a connected graph with no circuits. A set of trees is called a forest.

How to identify a tree?

A graph $G=(V,E)$ in which there is a unique path between every pair of vertices is a tree.

A graph $G=(V,E)$ such that $|E|=|V|-1$ that has no circuits is a tree.

There are various types of trees.

Trees can have various leaf and branch vertices, but they may only have one centre vertex and one root vertex.

Trees have a height.

Properties §

• In a tree, there exists a path between any two vertices.
• A tree with one or more vertices has at least a leaf vertex.