Tree (Graph Theory)
Calculus & Advanced MathA tree is a connected graph with no cycles, where any two vertices are connected by exactly one path.
Formula
|E| = |V| - 1
Definition
A tree is a connected graph with no loops or cycles. Like a real tree or a family tree, it branches out from a root with no circular routes back to where you started.
Example
A family tree is a graph where each person is a vertex and parent-child relationships are edges. There are no cycles because you cannot be your own ancestor.
Key Insight
Trees are the simplest connected graphs. They appear everywhere: file systems, organizational charts, parse trees in compilers, and decision trees in machine learning.
Definition
A tree on $n$ vertices has exactly $n-1$ edges, is connected, and has no cycles. These three properties are equivalent: any two imply the third. A spanning tree of a connected graph is a subgraph that includes all vertices and is a tree.
Example
Kruskal's and Prim's algorithms find the minimum spanning tree (MST) of a weighted graph: the spanning tree with minimum total edge weight. MSTs are used in network design to minimize cable length.
Key Insight
The number of spanning trees of $K_n$ (complete graph on $n$ vertices) is $n^{n-2}$, Cayley's formula. For $K_4$, that is $4^2 = 16$ spanning trees.
Definition
A tree $T = (V, E)$ is a connected acyclic graph. Equivalent characterizations: (1) $T$ is connected with $|E| = |V|-1$; (2) $T$ is acyclic with $|E| = |V|-1$; (3) any two vertices are connected by a unique path. Catalan numbers count the number of full binary trees with $n+1$ leaves.
Example
Prufer sequences provide a bijection between labeled trees on $n$ vertices and sequences of length $n-2$ from $\{1,\ldots,n\}$, proving Cayley's formula $|\text{spanning trees of } K_n| = n^{n-2}$ by a direct counting argument.
Key Insight
In data structures, balanced binary search trees (AVL, red-black) maintain logarithmic height, guaranteeing O(log n) search time. The tree structure is the reason binary search is efficient.