Trees

A precise introduction to trees, unique paths, edge counts, rooted structure, and spanning trees.

Vertices store objects; edges store selected relationships. A six-vertex network highlights one connected path in a contrasting colour. The numbered vertices and visible edges support direct checks of adjacency, routes, and cycles.

Precise definition

A tree is a connected undirected graph with no cycles. For a finite simple graph with $n$ vertices, the following are equivalent: it is a tree; it is connected with $n-1$ edges; it is acyclic with $n-1$ edges; or every two vertices have exactly one simple path between them.

Notation and mathematical language

A leaf has degree 1 (except conventions for a one-vertex rooted tree). In a rooted tree, each non-root vertex has one parent; descendants, depth, and height depend on the chosen root. A spanning tree of a connected graph contains every vertex and a subset of edges forming a tree.

Conceptual picture

Trees have just enough edges for connectivity. Removing any edge disconnects a tree, while adding any new edge between existing vertices creates exactly one cycle. The unique-path property explains why hierarchical routes and recursive decompositions are unambiguous.

Fully worked example

Interpretation and application

Trees model file systems, organizational hierarchies, expression parsing, decision processes, and minimum-cost network backbones. A spanning tree preserves reachability but discards redundant routes, so it also removes fault tolerance present in cycles.