Labeled Tree — Definition, Formula & Examples

A labeled tree is a tree (a connected graph with no cycles) in which every vertex is assigned a distinct label, typically the integers 1 through

n

. Because vertices are distinguishable, two labeled trees on the same vertex set are different if they have different edge sets.

A labeled tree on $n$ vertices is a connected, acyclic graph $T = (V, E)$ where $V = \{1, 2, \ldots, n\}$ and $|E| = n - 1$ . Two labeled trees $T_1 = (V, E_1)$ and $T_2 = (V, E_2)$ are considered distinct if and only if $E_1 \neq E_2$ .

Key Formula

T_n = n^{\,n-2}

Where:

$T_n$ = Number of distinct labeled trees on $n$ vertices
$n$ = Number of vertices, labeled $1, 2, \ldots, n$

How It Works

The key distinction between labeled and unlabeled trees is that labels make vertices individually identifiable. Swapping the positions of two vertices in an unlabeled tree might produce the same tree, but in a labeled tree it generally produces a different one. This is why the number of labeled trees on

n

vertices grows much faster than the number of unlabeled trees. Cayley's formula gives the exact count: there are

n^{n-2}

distinct labeled trees on

n

vertices. One standard proof of Cayley's formula uses Prüfer sequences, which establish a bijection between labeled trees on

n

vertices and sequences of length

n - 2

with entries from

\{1, 2, \ldots, n\}

Worked Example

Problem: How many distinct labeled trees exist on 4 vertices?

Apply Cayley's formula: Substitute

n = 4

into

T_n = n^{n-2}

T_4 = 4^{\,4-2} = 4^2 = 16

Verify by reasoning: Each labeled tree on 4 vertices corresponds to a unique Prüfer sequence of length 2 with entries from

\{1, 2, 3, 4\}

. There are

4 \times 4 = 16

such sequences, confirming the count.

Answer: There are 16 distinct labeled trees on 4 vertices.

Why It Matters

Labeled trees appear throughout combinatorics and computer science. Cayley's formula is a cornerstone result in enumerative graph theory and is tested frequently in discrete math courses. Prüfer sequences, which encode labeled trees, also have practical applications in network reliability analysis and random graph generation.

Common Mistakes

Mistake: Confusing labeled and unlabeled tree counts. For

n = 4

, students sometimes answer 2 (the number of unlabeled trees) instead of 16.

Correction: When vertices carry distinct labels, structurally identical trees with different label assignments count as different. Always use Cayley's formula

n^{n-2}

for labeled trees.