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

. □

A weighted graph and its minimum spanning tree (thick edges, total weight $1 + 2 + 3 + 4 = 10$ ):

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. Kruskal's algorithm processes the graph above in the order

{a, b}

(weight

1

{b, c}

(

2

{c, d}

(

3

), skipping

{a, c}

(

4

, creates cycle),

{a, d}

(

5

, creates cycle),

{b, d}

(

6

, creates cycle).

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 followers·107 articles

Trees and Forests: The Minimal Connected Structures

Folio Official

March 1, 2026

1. Definition and Equivalent Characterizations

Definition 1 (Tree and forest).

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

. □

A weighted graph and its minimum spanning tree (thick edges, total weight $1 + 2 + 3 + 4 = 10$ ):

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. Kruskal's algorithm processes the graph above in the order

{a, b}

(weight

1

{b, c}

(

2

{c, d}

(

3

), skipping

{a, c}

(

4

, creates cycle),

{a, d}

(

5

, creates cycle),

{b, d}

(

6

, creates cycle).

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 followers·107 articles

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

Share your expertise with the world

More from Folio Official

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences

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

Share your expertise with the world

More from Folio Official

Paths and Connectivity

Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems

Network Flows

Recurrence Relations and Counting: Solving Linear Recurrences