What Are Trees (Graphs)?

Trees, in the context of graph theory, are connected graphs with no cycles. A tree on N vertices contains exactly N minus 1 edges, and there is a unique simple path between every pair of vertices. These three properties, connectivity, acyclicity, and the specific edge count, are equivalent characterizations: any two of them imply the third. Trees constitute one of the most studied families of graphs because they represent the minimal connected structure, providing just enough edges to link every vertex without redundancy. They appear as a unifying concept across combinatorics, network theory, algorithm design, and the foundations of computer science.

The mathematical study of trees predates the formalization of graph theory. Gustav Kirchhoff employed tree decompositions in his 1847 analysis of electrical circuits to identify the independent current equations of a network. Arthur Cayley enumerated labeled trees in 1889 and established that the number of distinct labeled trees on N vertices equals N to the power of N minus 2, a result now known as Cayley's formula. These two historical applications, circuit analysis and combinatorial enumeration, remain among the most practically important uses of trees today.

Equivalent Characterizations and Formal Properties

A finite connected graph G is a tree if and only if any one of the following conditions holds: G has no cycles; G has exactly N minus 1 edges for N vertices; every pair of vertices in G is connected by a unique path; G is connected and the deletion of any single edge disconnects it; G is acyclic and the addition of any single edge creates exactly one cycle. These characterizations are interchangeable and choosing the most convenient one simplifies many proofs. The OpenStax Contemporary Mathematics reference on trees in graph theory illustrates several of these characterizations with worked examples. A forest is a graph in which every connected component is a tree; a forest on N vertices with K connected components has exactly N minus K edges.

Spanning Trees and Minimum Spanning Trees

Every connected graph G contains a spanning tree: a subgraph that includes all vertices of G and is itself a tree. When edges carry numerical weights, a minimum spanning tree (MST) is a spanning tree whose total edge weight is as small as possible. Kruskal's algorithm constructs an MST by greedily adding the lowest-weight edge that does not create a cycle, processing all edges in sorted order. Prim's algorithm builds the MST by expanding a single tree one vertex at a time, always attaching the least-cost available edge. Both run in O(E log E) time for a graph with E edges. The correctness of both algorithms follows from the cut property of MSTs: for any partition of the vertex set, the minimum-weight edge crossing the cut belongs to some MST. The ACM Digital Library archives early foundational work on MST algorithms that established the theoretical basis for modern implementations.

Rooted Trees and Tree Traversal

Designating one vertex as the root imposes a hierarchical direction on all edges, turning an unrooted tree into a rooted tree. In a rooted tree, each non-root vertex has a unique parent, and vertices with no children are called leaves. Rooted trees support standard traversal algorithms: depth-first traversal visits a vertex before or after its children (preorder and postorder), while breadth-first traversal visits all vertices at each depth level before descending. These traversal algorithms underpin a broad range of operations in compilers, XML processors, and expression evaluators. IEEE Transactions on Computers has covered tree traversal in the context of hardware-accelerated parsing and packet classification.

Applications

Trees in graph theory have applications in a range of fields, including:

• Network protocol design, where spanning tree protocols eliminate forwarding loops in switched networks
• Electrical circuit analysis, using tree and co-tree decompositions to write mesh and nodal equations
• Database and file system hierarchies, which are represented as rooted trees with ordered children
• Compiler front-ends, where parse trees and abstract syntax trees encode program structure
• Computational biology, where phylogenetic trees represent hypothesized evolutionary histories