Trees and Forests: The Minimal Connected Structures

We prove the equivalent characterizations of trees, establish the formula $|E|=|V|-1$, introduce rooted trees and Cayley's formula, and develop the theory of spanning trees and minimum spanning trees via Kruskal's and Prim's algorithms.

Folio Official

March 1, 2026

1 Definition and Equivalent Characterizations

Definition 1 (Tree and forest).

A connected graph with no cycles is called a tree. A graph with no cycles (not necessarily connected) is called a forest. Equivalently, a forest is a graph each of whose connected components is a tree.

Theorem 2 (Equivalent characterizations of trees).

For a graph

G

n

vertices, the following are equivalent:

$G$ is a tree (connected and acyclic).
There is exactly one path between every pair of vertices of $G$ .
$G$ is connected and $∣ E (G) ∣ = n - 1$ .
$G$ is acyclic and $∣ E (G) ∣ = n - 1$ .
$G$ is connected and every edge is a bridge.
$G$ is acyclic, but the addition of any new edge creates a cycle.

Proof.

(1) \Rightarrow (2)

: Since

G

is connected, a path exists between any two vertices. If two or more paths existed between some pair, their union would contain a cycle, contradicting the assumption.

(2) \Rightarrow (3)

: The existence of paths implies connectivity. We prove

∣ E ∣ = n - 1

by induction on

n

. For

n = 1

, we have

∣ E ∣ = 0 = n - 1

. Suppose

n \geq 2

. A vertex of degree

1

(a leaf) must exist: if every vertex had degree at least

2

, one could traverse edges from any starting vertex without immediate repetition, and finiteness would force a closed walk, hence a cycle, contradicting (2). Removing a leaf

v

and its incident edge yields a graph on

n - 1

vertices still satisfying (2). By induction, this graph has

n - 2

edges, so

G

has

n - 1

(3) \Rightarrow (4)

: Suppose

G

is connected with

∣ E ∣ = n - 1

and contains a cycle. Removing one edge of the cycle preserves connectivity, producing a connected graph on

n

vertices with

n - 2

edges. But every connected graph satisfies

∣ E ∣ \geq n - 1

, a contradiction.

(4) \Rightarrow (1)

: Let the connected components of

G

G_{1}, \dots, G_{c}

with

∣ V (G_{i}) ∣ = n_{i}

. Each

G_{i}

is a tree (connected and acyclic), so by

(1) \Rightarrow (3)

it has

n_{i} - 1

edges. Thus

∣ E (G) ∣ = \sum (n_{i} - 1) = n - c

. Since

∣ E (G) ∣ = n - 1

, we get

c = 1

, i.e.,

G

is connected.

(1) \Rightarrow (5)

: Every edge of a tree is a bridge, for if an edge

e

lay on a cycle, the tree would contain a cycle — a contradiction.

(5) \Rightarrow (1)

: Connectivity is assumed. If a cycle existed, any edge

e

on that cycle would satisfy the property that

G - e

remains connected (the cycle provides an alternative route), so

e

would not be a bridge — a contradiction.

(1) \Rightarrow (6)

: Acyclicity is given. Adding a non-edge

{u, v}

creates a cycle together with the unique

u

v

path in the tree.

(6) \Rightarrow (1)

: Acyclicity is given. If

G

were disconnected, adding an edge between vertices in different components would not create a cycle, contradicting the hypothesis. □

2 Rooted Trees

Definition 3 (Rooted tree).

A rooted tree is a tree

T

in which a distinguished vertex

r

has been designated as the root. The unique path from

r

to each vertex induces a parent–child relation: if

u

lies on the path from

r

v

and

{u, v} \in E (T)

, then

u

is the parent of

v

and

v

is a child of

u

. A vertex with no children is called a leaf.

3 Cayley's Formula

Theorem 4 (Cayley's formula).

The number of labeled trees on

n

labeled vertices

{1, 2, \dots, n}

n^{n - 2}

Proof.

We give a proof via Prü

n

vertices and sequences

(a_{1}, \dots, a_{n - 2})

with each

a_{i} \in {1, \dots, n}

From tree to sequence. Given a tree

T

, repeat the following

n - 2

times: find the leaf with the smallest label, record the label of its unique neighbor as

a_{i}

, and remove the leaf.

From sequence to tree. Given a sequence

(a_{1}, \dots, a_{n - 2})

, reconstruct the tree as follows. Set

S = {1, \dots, n}

. For

i = 1, \dots, n - 2

: let

v

be the smallest element of

S

that does not appear in

(a_{i}, \dots, a_{n - 2})

, add the edge

{v, a_{i}}

, and remove

v

from

S

. Finally, connect the two elements remaining in

S

by an edge.

One verifies that these two maps are mutual inverses, establishing a bijection. Since there are

n^{n - 2}

possible sequences, the result follows. □

Example 5.

For

n = 3

, we get

3^{1} = 3

. The three labeled trees on

{1, 2, 3}

have edge sets

{{1, 2}, {1, 3}}

{{1, 2}, {2, 3}}

, and

{{1, 3}, {2, 3}}

4 Spanning Trees and Minimum Spanning Trees

Definition 6 (Spanning tree).

A spanning tree of a connected graph

G

is a subgraph of

G

that contains all vertices of

G

and is a tree.

Theorem 7.

Every connected graph has a spanning tree.

Proof.

G

is connected and acyclic, it is already a tree. Otherwise,

G

contains a cycle; removing any edge of this cycle preserves connectivity. Since the number of edges is finite, repeating this process eventually yields a tree. □

Definition 8 (Minimum spanning tree).

Given a connected graph

G

with edge weights

w : E \to R

, a spanning tree

T

that minimizes

w (T) = \sum_{e \in E (T)} w (e)

is called a minimum spanning tree (MST).

Theorem 9 (Cut property).

When all edge weights are distinct, the minimum-weight edge crossing any cut (i.e., any partition

(S, V ∖ S)

) belongs to every MST.

Proof.

Let

e = {u, v}

(with

u \in S

v \in V ∖ S

) be the minimum-weight edge crossing the cut, and suppose

e

does not belong to some MST

T

. The unique

u

v

path in

T

crosses the cut an odd number of times, so it contains another edge

f

crossing the cut. The tree

T - f + e

is also a spanning tree, and

w (e) < w (f)

gives

w (T - f + e) < w (T)

, contradicting the minimality of

T

. □

Remark 10 (Kruskal's algorithm).

Sort the edges in nondecreasing order of weight and add each edge unless it creates a cycle. Using Union-Find, this runs in

O (m lo g m)

time and correctly produces an MST.

Algorithm 1: Kruskal's Algorithm

Input:

Connected graph

G = (V, E)

, weight function

w : E \to R

Output:

Edge set

T

of a minimum spanning tree

T \leftarrow \emptyset

Sort the edges by weight in nondecreasing order:

e_{1}, e_{2}, \dots, e_{m}

for all

v \in V

MakeSet(

v

)

// Initialize Union-Find

end for

for

i = 1

m

Let

e_{i} = {u, v}

Find (u) \neq = Find (v)

T \leftarrow T \cup {e_{i}}

Union(

u, v

)

end if

end for

return

T

Remark 11 (Prim's algorithm).

Starting from a single vertex, repeatedly add the minimum-weight edge that connects the current tree to a vertex not yet in the tree. Using a priority queue, this runs in

O (m lo g n)

time.

Algorithm 2: Prim's Algorithm

Input:

Connected graph

G = (V, E)

, weight function

w

, starting vertex

r

Output:

Edge set

T

of a minimum spanning tree

T \leftarrow \emptyset

S \leftarrow {r}

key [r] \leftarrow 0

for all

v \in V ∖ {r}

key [v] \leftarrow + \infty

end for

Insert all vertices into priority queue

Q

with key values

while

Q \neq = \emptyset

u \leftarrow ExtractMin (Q)

S \leftarrow S \cup {u}

u \neq = r

T \leftarrow T \cup {{u, parent [u]}}

end if

for all

(u, v) \in E

with

v \in Q

w (u, v) < key [v]

key [v] \leftarrow w (u, v)

parent [v] \leftarrow u

DecreaseKey(

Q, v, key [v]

)

end if

end for

end while

return

T

Graph Theory Discrete Mathematics Textbook Trees Spanning Trees Minimum Spanning Trees

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 フォロワー·105 記事

Trees and Forests: The Minimal Connected Structures

1 Definition and Equivalent Characterizations

2 Rooted Trees

3 Cayley's Formula

4 Spanning Trees and Minimum Spanning Trees

あなたの専門知識を世界に発信しよう

Folio Officialの他の記事

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry