A graph is made up of nodes and edges. A directed graph consists of a set of nodes and a set of directed edges. Most graphs are undirected.

Applications of graphs include transportation networks, communication networks, information networks, social networks, and dependency networks.

A path traversing a graph is simple if all its vertices are distinct from one another. A cycle is a series of nodes that cycles back to where it began. In a directed graph, the path or cycle must respect the directionality of edges.

An undirected graph is connected if there is a path for every pair of nodes. The distance between two nodes is the minimum number of edges in the path.

A tree is an undirected graph not containing a cycle. Relationships between adjacent nodes are define by ancestor or descendant. A leaf is a node with no descendants.

Every n-node tree has exactly n-1 edges.

Let G be an undirected graph on n nodes. Any two of the following statements implies the third:

1. G is connected
2. G does not contain a cycle
3. G has n-1 edges