A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
A tree is a connected acyclic graph. It has exactly n−1 edges for n vertices, a unique path between any two vertices, and no cycles. Trees generalize to forests (disjoint unions of trees). Rooted trees model hierarchies, with roots at top and leaves at bottom.
Recognize that any two of these properties imply the third: connected, n−1 edges, acyclic. Build spanning trees of given graphs. Use tree terminology: parent, child, ancestor, depth, height.
Not all trees are rooted; an unrooted tree has no distinguished root. A path graph and a star graph are both trees but very different structurally.
From your work on connectivity and components, you know that a connected graph has a path between every pair of vertices. A tree adds one more constraint: no cycles. These two properties together — connected and acyclic — turn out to be very restrictive in a precise way. A tree on n vertices has exactly n−1 edges, no more and no fewer. This is not a coincidence; it follows from the structure itself. To keep a graph connected you need enough edges, but every extra edge beyond n−1 creates a cycle. Trees are, in a sense, the *minimal* connected graphs — remove any single edge and the graph falls apart into two components.
The power of trees is captured in three equivalent characterizations of the same object. A graph G on n vertices is a tree if and only if any of these holds: (1) G is connected and acyclic; (2) G is connected and has n−1 edges; (3) G is acyclic and has n−1 edges. You only ever need two of the three conditions to guarantee the third. This means if someone hands you a graph and tells you "it's connected with exactly n−1 edges," you automatically know it's acyclic without checking. These equivalences are often proved by induction on n using the fact that every tree with at least two vertices has a leaf — a vertex of degree 1 — which you can remove to get a smaller tree.
Rooted trees add a hierarchy. Pick any vertex as the root, and the tree inherits a natural parent-child structure: every vertex (except the root) has a unique parent — the neighbor one step closer to the root — and its children are the neighbors one step farther. Vertices with no children are leaves. The depth of a vertex is its distance from the root; the height of the tree is the maximum depth. This parent-child structure is pervasive in computer science: file systems, parse trees, decision trees, and binary search trees are all rooted trees. The underlying mathematical object is always the same — connected, acyclic, n−1 edges — but the labeling of a root imposes an orientation.
A forest is simply the generalization to disconnected cases: a disjoint union of trees. If a forest has k trees and n total vertices, it has exactly n−k edges. Forests matter because spanning trees of connected graphs, minimum spanning tree algorithms, and independent sets in graphic matroids are all forests in disguise.