Tree (Graph Theory)
A 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. A tree on $n$ vertices has exactly $n-1$ edges, is connected, and has no cycles, three equivalent properties where any two imply the third; a spanning tree of a connected graph is a subgraph that includes all vertices and is a tree. Equivalent characterizations of a tree $T = (V,E)$: connected with $|E|=|V|-1$; acyclic with $|E|=|V|-1$; or any two vertices connected by a unique path; Catalan numbers count the full binary trees with $n+1$ leaves.
Example
A family tree is a graph where each person is a vertex and parent-child relationships are edges, with no cycles because you cannot be your own ancestor. Kruskal's and Prim's algorithms find the minimum spanning tree (MST) of a weighted graph, the spanning tree with minimum total edge weight, used in network design to minimize cable length. Cayley's formula states the number of spanning trees of $K_n$ (the complete graph on $n$ vertices) is $n^{n-2}$; Prufer sequences prove this by a bijection between labeled trees and sequences of length $n-2$.
Key Insight
Trees are the simplest connected graphs, appearing everywhere: file systems, organizational charts, parse trees in compilers, and decision trees in machine learning. In data structures, balanced binary search trees (AVL, red-black) maintain logarithmic height, guaranteeing O(log n) search time, the reason binary search is efficient.