Trees — Mathematics Knowledge System

Overview

A tree is an undirected graph in which every pair of distinct vertices is connected by exactly one path — equivalently, a connected, acyclic graph. A forest is a disjoint union of trees (an acyclic graph that need not be connected). Trees are the simplest nontrivial graphs and underlie hierarchical structures everywhere: file systems, organization charts, family genealogies, decision trees, and the parse trees compilers build from source code.

Intuition

Imagine a graph with just enough edges to keep everything connected, and not one edge more. Add any extra edge to a tree and you create a cycle (a redundant path between two vertices); remove any edge and the tree falls into two disconnected pieces. That razor's-edge property — minimally connected — is what makes a tree a tree.

Interactive Graph

Formal Definition

Definition

A tree is a graph satisfying any one of several equivalent conditions (each implies the others): connected and acyclic; connected with exactly n-1 edges on n vertices; acyclic with exactly n-1 edges; or having a unique path between every pair of vertices.

T = (V, E),\quad |E| = |V| - 1,\quad T \text{ connected, acyclic}

A tree on n = |V| vertices has exactly n − 1 edges

\forall u, v \in V,\ \exists! \text{ path from } u \text{ to } v

Uniqueness of paths — the defining property of a tree

Notation

Notation	Meaning
$T$	A tree
$\deg(v) = 1$	A leaf (or pendant vertex) — a vertex of degree 1
$r$	The distinguished root vertex in a rooted tree

Properties

Edge count

|E(T)| = |V(T)| - 1

Example: A tree on 12 vertices has exactly 11 edges

Every tree with ≥2 vertices has at least 2 leaves

\exists\, u \neq v:\ \deg(u) = \deg(v) = 1

Adding one edge to a tree creates exactly one cycle

T + e \text{ contains exactly one cycle, for any } e \notin E(T)

Spanning tree

\text{A spanning tree of connected } G=(V,E) \text{ is a subgraph } T=(V,E') \text{ that is a tree.}

Applications

Binary search trees, heaps, tries, and parse trees are all rooted trees; file systems and DOM trees are literal hierarchical trees.

Worked Examples

A connected graph on n vertices is a tree iff it has exactly n−1 edges (this rules out cycles automatically, since a connected graph with a cycle has ≥ n edges).
$|E| = 8 - 1 = 7$

Answer: Yes — connected with exactly n−1 = 7 edges forces it to be acyclic, hence a tree.

Practice Problems

Difficulty 3/10

A forest has 20 vertices and 3 connected components (i.e. 3 trees). How many edges does it have?

Difficulty 2/10

Which statement is FALSE about trees?

A tree is connectedA tree has no cyclesA tree can have multiple edges between the same pair of verticesA tree on n vertices has exactly n−1 edges

Difficulty 4/10

A computer's file system is a tree: folders contain files and subfolders. If there are 500 folders/files total (nodes), how many parent–child links (edges) are there, and why is there exactly one path to any file?

Difficulty 5/10

A balanced binary search tree stores 1,000,000 records. Roughly how many comparisons are needed to find a record, and why is the tree structure the reason?

Common Mistakes

Common Mistake

Believing any connected graph with n−1 edges must be a tree only if you also check acyclicity separately.

For a graph on n vertices, 'connected' + 'n−1 edges' already forces acyclicity — you get the tree property for free from vertex/edge counting, no separate cycle check needed.

Common Mistake

Assuming a 'rooted tree' and a 'tree' are different mathematical objects.

A rooted tree is just a tree (in the graph-theory sense above) with one vertex designated as the root — the underlying graph structure is identical; the root only adds a notion of parent/child direction.

Quiz

Summary

A tree is a connected, acyclic undirected graph; a forest is a disjoint union of trees.
A tree on n vertices always has exactly n−1 edges — this single number characterizes trees among connected graphs.
Every tree with 2+ vertices has at least two leaves (degree-1 vertices).
There is a unique path between any two vertices in a tree.
Trees underlie hierarchical data structures (BSTs, tries, file systems) and minimum spanning tree algorithms.

References

WebsiteWikipedia — Tree (graph theory)