Graph Concepts

Trees and forests

A tree is a connected graph with no cycles. These are trees:

A forest is a graph with no cycles. It may or may not be connected. So a single tree is a forest, and a forest consists of one or more trees.

Trees are often used for listing possibilities systematically. The tree below shows how a tournament among five teams is organized. The vertices represent the status of teams (playing games, out, bye, champion) at various times; the edges represent the teams.

A tree for a tournament

This tree shows the ways teams A and B could play each other until one wins two games:

Another tournament tree

Each vertex represents a game, and is labeled with the winner.