How many distinct labeled trees can be formed on n labeled vertices?

Concept

Cayley’s formula states that the number of distinct labeled trees on n labeled vertices is nn−2.

An equivalent viewpoint uses Prüfer codes: every such tree corresponds bijectively to one sequence of length n−2 formed from the n vertex labels.

Application

The question asks for trees on n labeled vertices, so Cayley’s formula applies directly.

1. Each of the n−2 positions in a Prüfer sequence can contain any one of the n vertex labels.

2. By the multiplication rule, the number of sequences is n multiplied by itself n−2 times, which is nn−2.

Cross-check

For n=3, the formula gives 33−2=3. Indeed, on three labeled vertices, there are three choices for the center of the two-edge path.

Result

Therefore, the number of distinct labeled trees is nn−2.