Tree (graph theory)
A tree in graph theory is a connected, undirected graph containing no cycles, which means any two vertices are joined by exactly one unique path. A tree with n vertices always has exactly n − 1 edges. Trees are foundational data structures in computer science (binary search trees, heaps, syntax trees) and appear in network design, organisational hierarchies, and phylogenetics.
Key Formula
Number of edges = Number of vertices − 1
LaTeX: |E| = |V| - 1
| Symbol | Meaning | Unit |
|---|---|---|
| |E| | Number of edges in the tree | none |
| |V| | Number of vertices in the tree | none |
Worked Example
Problem
A company has a hierarchical org chart with 1 CEO, 3 VPs each reporting to the CEO, and 4 employees each reporting to one VP. Model this as a tree and verify the edge count.
Solution
Step 1: Identify vertices: 1 CEO + 3 VPs + 12 employees = 16 vertices total. Step 2: Identify edges (reporting lines): CEO→VP1, CEO→VP2, CEO→VP3 = 3 edges. Each VP has 4 employees: 3 × 4 = 12 edges. Step 3: Total edges = 3 + 12 = 15. Step 4: Verify using tree formula: |E| = |V| − 1 = 16 − 1 = 15. ✓ Step 5: Confirm it is a tree: connected (everyone links to CEO), no cycles (each employee has exactly one manager).
Answer
16 vertices, 15 edges. Formula |E| = |V| − 1 verified. The org chart forms a valid tree.
Properties and Types of Trees in Graph Theory
| Type | Description | Key Property | Application |
|---|---|---|---|
| Free Tree | Unrooted connected acyclic graph | |E| = |V| − 1 | Spanning trees, networks |
| Rooted Tree | One vertex designated as root | Parent-child relationships | Org charts, DOM trees |
| Binary Tree | Each node has at most 2 children | Max 2 children per node | Binary search, heaps |
| Spanning Tree | Tree connecting all vertices of a graph | Subgraph of original graph | Minimum spanning tree (Kruskal) |
| Balanced Tree | All leaves at same or adjacent levels | Height ≈ log₂(n) | AVL trees, efficient search |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Graph Theory
Graph theory is the branch of mathematics that studies graphs — mathematical structures consisting of vertices (nodes) connected by edges (links) used to model pairwise relationships between objects. It was founded by Leonhard Euler in 1736 when he solved the Königsberg bridge problem. Graph theory underpins computer networks, social network analysis, circuit design, scheduling algorithms, and shortest-path computations.
Graph Path
A path in a graph is a sequence of vertices in which each consecutive pair is connected by an edge and no vertex is repeated. The length of a path is defined as the number of edges it traverses. Paths are central to graph algorithms such as Dijkstra's shortest-path algorithm, breadth-first search, and depth-first search, which are used in navigation systems, network routing, and AI planning.
Euler Path
An Euler path (or Eulerian path) is a trail in a graph that visits every edge exactly once, without necessarily returning to the starting vertex. An Euler circuit (or Eulerian circuit) is an Euler path that begins and ends at the same vertex. A connected graph has an Euler path if and only if it has exactly zero or two vertices of odd degree; if two odd-degree vertices exist, the path must start and end at those vertices.
The use of "tree" as a mathematical term was introduced by Arthur Cayley in 1857 in his paper on the enumeration of chemical isomers (rooted trees representing molecular structures). The biological metaphor was apt: a tree grows without forming loops and has a natural branching hierarchy.