Trees

A tree is a connected graph with no cycles. That means there is a path between any two vertices, and you cannot start at one vertex and return to it by following a sequence of edges without repeating any edge or vertex (except possibly the start/end).

Important properties

• A tree with $n$ vertices has exactly $n-1$ edges.

• There is exactly one path between any two vertices in a tree.

• Adding any edge to a tree creates a cycle.

• Removing any edge from a tree disconnects it.