1 Basic Definitions and Properties
1.1 Graph-theoretic definition of a tree
In discrete mathematics, a tree is a graph that is both connected and acyclic. In an undirected setting, it contains vertices connected by edges such that every pair of vertices is reachable, yet no cycle exists.
1.2 Connectivity and acyclicity
Connectivity means there is at least one path between any two vertices. Acyclicity means the graph contains no closed walk that starts and ends at the same vertex while using distinct edges (equivalently, no simple cycle).
1.3 Trees as minimal connected graphs
A tree is a minimal connected graph in the sense that removing any edge destroys connectivity. If an edge is deleted from a connected acyclic graph, the remaining structure splits into two components corresponding to the endpoints of the removed edge.
1.4 Degree sum and number of edges
Let a tree have \(n\) vertices and \(m\) edges. A standard fact for acyclic connected graphs is \[ m=n-1. \] The degree sum formula states that for any finite graph, \[ \sum_{v} \deg(v)=2m. \] Thus for a tree, \[ \sum_{v} \deg(v)=2(n-1). \] These relationships are frequently used to constrain degree patterns and count edges indirectly.
2 Equivalent Characterizations
2.1 Characterizations using cycles
A connected graph is a tree if and only if it has no cycles. More generally, several “no-cycle” statements are equivalent in this context: for a connected graph, the absence of any simple cycle already forces acyclicity globally.
2.2 Characterizations using paths
A graph is a tree if and only if between every pair of vertices there exists exactly one simple path. Existence follows from connectivity, while uniqueness fails precisely when a cycle provides an alternative route.
2.3 Characterizations using distances and diameter
Distances in a tree are well-defined as the lengths (number of edges) of shortest paths. The diameter is the maximum distance between any two vertices. While diameter alone does not characterize trees among all graphs, tree structure guarantees that shortest paths behave rigidly and are unique for any chosen pair.
2.4 Characterizations using spanning subgraphs
A graph on \(n\) vertices is a tree precisely when it is a spanning subgraph that is connected and has \(n-1\) edges. Since any connected graph with \(n-1\) edges cannot contain a cycle, this provides another practical criterion for recognizing trees.
3 Counting and Enumeration
3.1 Number of labeled trees (Cayley’s formula)
For \(n\ge 2\), the number of labeled trees on a vertex set of size \(n\) is \[ n^{n-2}, \] known as Cayley’s formula. “Labeled” means vertices are distinguishable. Cayley’s result is foundational in random tree models and enumerative combinatorics.
3.2 Unlabeled trees and growth intuition
When labels are removed, counting becomes more intricate because many configurations are isomorphic. The number of unlabeled trees grows rapidly with \(n\), but there is no simple closed-form expression analogous to Cayley’s formula; instead, one uses generating functions, recurrence relations, or partition-based methods to enumerate nonisomorphic types.
3.3 Counting subtrees and induced subgraphs
A subtree often refers to a connected induced subgraph; counting such structures can be done through combinatorial casework or dynamic programming on the tree itself. Induced subgraph counts are sensitive to whether “subtree” must be induced, rooted, or required to preserve adjacency relationships.
3.4 Prüfer sequences and their applications
A Prüfer sequence is a string of length \(n-2\) associated with a labeled tree. The mapping between labeled trees and Prüfer sequences is bijective, enabling easy counting (recovering \(n^{n-2}\)) and supporting constructive generation. Prüfer-style encodings also help analyze degree distributions: the number of times a label appears in the sequence relates to the degree of that vertex in the original tree.
4 Rooted Trees and Hierarchies
4.1 Rooted vs. unrooted trees
A rooted tree is a tree with one distinguished vertex called the root. Rooting transforms undirected structure into a directed hierarchical viewpoint, enabling parent/child relations and natural definitions of levels.
4.2 Parent/child, ancestor/descendant relationships
With a root fixed, each non-root vertex has a unique neighbor on the path to the root, called its parent. The remaining neighbors are its children. This induces partial orders: an ancestor of a vertex is any node on the path from the root to that vertex, and descendants are vertices for which the given node lies on their root path.
4.3 Level sets and height
Vertices can be grouped by their distance from the root, producing level sets. The height is the maximum level index among vertices. These measures are central in analyzing recursion depth, balancing properties, and performance of tree-based algorithms.
4.4 Branching structure and degree constraints
In rooted settings, constraints on degrees become constraints on branching: a vertex with \(k\) children has total degree \(k+1\) if it is not the root (the extra \(1\) accounts for its parent). Such bookkeeping simplifies the study of restricted families like binary trees and regular rooted trees.
5 Special Classes of Trees
5.1 Binary trees and degree limits
A binary tree is commonly defined so that each vertex has at most two children. In rooted graphs, this yields degree limits: non-root vertices have total degree at most three, while the root has total degree at most two. Variants differ on whether “exactly two” children are allowed or whether one-child nodes occur.
5.2 Ordered (plane) trees
An ordered or plane tree treats the children of each vertex as having a left-to-right order. This changes enumeration: two trees that are isomorphic as un-ordered trees may count separately because different child permutations produce distinct plane structures.
5.3 Free trees vs. rooted ordered trees
“Free” typically indicates trees without a specified root, while “rooted ordered” adds both a root and an order among siblings. These extra structure choices substantially affect counting and how recursion is formulated, since the root anchors recursive subproblems and the sibling order determines the combinatorics of grafting operations.
5.4 Spanning trees and tree families
In a general graph, a spanning tree is a tree that includes all vertices. A single graph can have many spanning trees, forming a “family” tied to connectivity and structure. Spanning tree families appear naturally in probabilistic models and in algorithmic techniques that replace complex graphs with tree-like backbones.
6 Tree Traversal and Algorithms
6.1 Depth-first search on trees
Depth-first search (DFS) explores along a path as far as possible before backtracking. On a tree, DFS visits vertices without ambiguity about cycles, making it especially clean: every edge leads either to an unvisited child or back to the parent.
6.2 Breadth-first search on trees
Breadth-first search (BFS) explores in waves by distance from a start vertex. Because trees have unique simple paths, BFS levels correspond exactly to distances, which simplifies proofs about correctness and shortest-path properties.
6.3 Recursive traversal patterns
Many traversal procedures can be described recursively: process the current vertex, then recursively handle each child sub-tree. This recursive viewpoint aligns with rooted trees and supports straightforward reasoning about runtime and visited-state invariants.
6.4 Using traversal for verification and reconstruction
Traversal can verify structural claims, such as checking that a proposed adjacency description is acyclic and connected. It also supports reconstruction tasks: for example, given parent pointers or a rooted traversal order, one can rebuild the tree representation as long as the needed constraints are consistent.
7 Paths, Centers, and Distances
7.1 Unique simple paths
In a tree, between any two vertices there is a unique simple path. This uniqueness underpins many distance calculations, ancestor relations, and algorithmic routines that depend on determinism of routing.
7.2 Distances and eccentricity
The distance between vertices is the number of edges on their unique path. The eccentricity of a vertex is the maximum distance from that vertex to any other vertex. Trees allow efficient reasoning about eccentricity because farthest nodes often lie at endpoints of diameter paths.
7.3 Tree center and radius/diameter
The diameter is the maximum distance between any pair of vertices. The center of a tree is the set of vertices minimizing the maximum distance to all others. The radius is that minimal maximum distance, and a classic relationship is that the radius is determined by the diameter: the center lies midway along any diameter path (possibly a single vertex or an edge).
7.4 Lowest common ancestor (LCA) concepts
For rooted trees, the lowest common ancestor of two vertices is the deepest vertex that is an ancestor of both. LCA is a core concept in answering queries about paths, distances, and hierarchical relationships efficiently, often via preprocessing techniques or binary lifting.
8 Trees in Dynamic Programming and Recurrences
8.1 DP on tree decompositions (tree-shaped dependencies)
Dynamic programming on trees leverages the fact that many problems decompose along a hierarchical structure. When subproblems correspond to subtrees, the dependencies form a tree-shaped graph, enabling bottom-up or top-down computation with controlled overlap.
8.2 Tree recurrences via subproblem splitting
A typical recurrence expresses the value for a node in terms of values for its children subproblems. Because a tree has no cycles, combining child results is straightforward: once the local decision at a node is fixed, the remaining work splits cleanly among disjoint subtrees.
8.3 Rerooting techniques (high-level idea)
Rerooting addresses the situation where answers are needed for all choices of root or for queries involving different reference points. At a high level, it performs two phases of propagation: one phase computes information from leaves toward an initial root, and a second phase propagates “complement” information outward so each node can be treated as a root efficiently.
8.4 Complexity considerations
Tree-based DP often runs in time proportional to the number of vertices times the cost of combining child states. Since trees have \(n-1\) edges, the absence of cycles helps prevent exponential blowups. Careful state design is crucial: overly detailed DP states can dominate runtime even when the structure is simple.
9 Spanning Trees in Graphs
9.1 Existence and relevance to connected graphs
A connected graph always has at least one spanning tree. This follows from repeatedly removing edges that lie on cycles until no cycles remain, yielding a maximal acyclic connected subgraph.
9.2 Counting spanning trees (overview)
Counting spanning trees is a classical enumerative problem. The number depends on how richly the graph is connected beyond mere connectivity, and it can differ dramatically even for graphs with similar size. In practice, counting often involves matrix-based methods or specialized formulas for certain graph families.
9.3 Constructive methods
Constructing a spanning tree can be done by algorithms that grow a tree while maintaining acyclicity, such as iterative edge addition while avoiding cycles. For weighted graphs, construction may also integrate optimization principles depending on the target objective.
9.4 Relationship to minimum spanning trees (conceptual)
While spanning trees exist regardless of weights, minimum spanning trees (MSTs) select among them according to total edge weight. Conceptually, an MST is a spanning tree that optimizes a global criterion; thus MST algorithms can be viewed as structured spanning tree construction under an optimization constraint.
10 Applications and Representations
10.1 Modeling hierarchical data
Trees naturally represent hierarchical structures, including category systems and file directory layouts. The parent-child relationship captures inclusion or containment, while the acyclic property prevents contradictory or circular references.
10.2 Parse trees and syntactic structure (overview)
In formal language processing, parse trees represent how a sentence conforms to a grammar. Tree nodes correspond to grammatical constructs, and their branching reflects production rules. Even in implementations that avoid explicit tree objects, the underlying reasoning is tree-shaped.
10.3 Decision trees in computation (high level)
A decision tree models a sequence of tests leading to outcomes. Although decision diagrams can be more general than trees, the fundamental idea is branching without revisiting states along a root-to-leaf route, aligning closely with tree mechanics.
10.4 Organization charts and branching process intuition
Organization charts encode reporting lines in a tree-like structure when there is a single chain of command. More broadly, branching processes in probabilistic modeling also use tree-like growth: entities reproduce independently across generations, and the genealogy forms a tree.
11 Common Problems and Proof Techniques
11.1 Proving uniqueness of paths
To show uniqueness, one typically argues that existence is guaranteed by connectivity, and then assumes two distinct simple paths between the same vertices. Their union would contain a cycle, contradicting acyclicity.
11.2 Induction on number of vertices
Induction on \(n\) is a frequent approach. Because trees always have leaves (vertices of degree 1), proofs often remove a leaf to reduce the problem size, apply the inductive hypothesis, and then extend the argument back to the original tree.
11.3 Invariants and edge/degree arguments
Many results follow from invariants like the relationship \(m=n-1\) or from degree-sum constraints. By counting degrees or edges in substructures, one can rule out impossible configurations, derive existence statements (e.g., there must be leaves), and establish structural bounds.
11.4 Bijective reasoning via Prüfer-style mappings
Bijective proofs often use Prüfer sequences or related encodings to translate tree questions into questions about strings or combinatorial objects with simpler counting. The key technique is to define an encoding that is reversible, ensuring that counting or structural claims transfer exactly between worlds.