Definition and Properties of Trees
You'll learn what makes a tree special: a connected graph with no cycles, and why several seemingly different definitions are actually equivalent.
What Is a Tree?
In graph theory, a tree is a connected graph that contains no cycles. Think of it like a family tree or an organizational chart—you can travel from any person to any other by following connections, but you'll never loop back to where you started without retracing your steps.
Trees are surprisingly common in mathematics and computer science because they represent hierarchical structures naturally.
Equivalent Characterizations
Here's what makes trees fascinating: several different properties all define the exact same structure. A graph with n vertices is a tree if and only if any one of these is true:
- Connected and acyclic – The graph is connected and has no cycles (the definition above)
- Minimally connected – It's connected, but removing any single edge disconnects it
- Maximally acyclic – It has no cycles, but adding any edge creates one
- Unique path property – There's exactly one path between any two vertices
- Edge count formula – It's connected and has exactly n - 1 edges
All five statements describe the same object! For example, if a connected graph has 10 vertices and it's a tree, it must have exactly 9 edges—no more, no less.
Why This Matters
Trees are the "skeleton" of connectivity. They have just enough edges to keep everything connected, with no redundancy. This makes them efficient for modeling hierarchies, searching algorithms, and network design.
Key Takeaway: A tree is a connected, acyclic graph, equivalently characterized as having exactly n - 1 edges, unique paths between vertices, or being minimally connected or maximally acyclic.