LEC DMAT 7

Cayley’s theorem

Definition 205.1(Tree).

A tree is a minimally connected graph.

Definition 205.2(Cycle).

A cycle is a sequence of distinct vertices $u_1,u_2,\dots u_k$ where $\{u_i,u_{i+1}\}\in E$ for all $1\le i\le k-1$ and $\{u_k,u_1\}\in E$.

Theorem 205.3(Theorem).

A tree is a connected graph without cycles.

Theorem 205.4(Cayley's).

The number of labelled trees on $n$ vertices is $n^{n-2}$.

Refer Cameron (2001, p. 38).

Alternate proof exists using Prüfer sequences.

---

References

Cameron, P. J. (2001). Combinatorics: Topics, Techniques, Algorithms (Transferred to digital printing). Cambridge Univ. Press.