📂Graph Theory

Label Tree and Cayley's Theorem

Definition

A labeled tree is a tree in which each vertex is assigned a distinct number.

Description

The concept of labeling is different from simply determining whether the elements in a set of vertices are the same or different. For example, the following two graphs are essentially considered the same labeled tree, despite having different labels written on them.

$$ 1-2-3 \\ a-b-c $$ Of course, because they are graphs, the following two are considered the same. $$ 1-2-3 \\ 3-2-1 $$ However, the following two graphs are clearly distinguished when labeled. $$ 1-2-3 \\ 2-3-1 $$ Counting the number of such labeled trees involves a much larger set of possibilities than combinatorial permutations. While permutations involve distinct elements arranged in order, the case with trees becomes significantly more complex as branches extend. Fortunately, the following theorem is known regarding this.

Cayley’s Theorem ¹

There are $n^{n-2}$ possible labeled trees with $n$ vertices.

For instance, if $n=2$, there are simply $2^{2-2} = 1$ ways that $1$ and $2$ are connected. If $n=3$, there are $3^{3-2} = 3$ possible cases as shown below. $$ 2-1-3 \\ 3-2-1 \\ 1-3-2 $$

Significance

Counting the number of labeled trees can be applied, for example, in fields like chemistry to predict and discover yet-undiscovered molecular structures. Thus, pure graph theory, intertwined with combinatorics, continues to attract significant interest and is actively researched.