Lagmental Vicfred

Prüfer Codes Count Labeled Trees by Vicfred

tags: mathematics, graph enumeration, chromatic polynomials, matroids

Deleting the smallest leaf repeatedly gives a bijection between labeled trees and sequences of length n minus two. A small computation will anchor the general statement before the abstraction takes over.

Statement

Graph invariants often satisfy deletion--contraction recurrences. The chromatic polynomial \(P_G(q)\) and Tutte polynomial \(T_G(x,y)\) package many counts into algebraic form.

$$ T\ \text{tree on }[n]\longleftrightarrow(a_1,\ldots,a_{n-2})\in[n]^{n-2} $$

There are two layers here: the object \(\mathsf D\) and the law \(\mathsf C\). Writing them separately makes the direction of \(\Longrightarrow\) visible and keeps an accidental converse from slipping in.

$$ \#\{\text{labeled trees on }[n]\}=n^{n-2} $$

Worked algebra

A worked instance is useful here because it exposes every index that the compressed statement hides.

$$ \deg_T(v)=1+\#\{i:a_i=v\} $$

Conceptual compression

The abstraction earns its keep by explaining why the same computation reappears. The notation compresses repeated reasoning without erasing the hypothesis that licenses it.

$$ \begin{aligned} \mathsf{D}\;&:\quad T\ \text{tree on }[n]\longleftrightarrow(a_1,\ldots,a_{n-2})\in[n]^{n-2},\\[5pt] \mathsf{C}\;&:\quad \#\{\text{labeled trees on }[n]\}=n^{n-2}. \end{aligned} $$

Caveat

Deletion--contraction must distinguish loops and bridges. Applying the generic edge recurrence to either special case changes the invariant incorrectly.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \#\{\text{labeled trees on }[n]\}=n^{n-2} \end{gathered}} $$

The notation is dense, but it is doing honest work: every delimiter records scope and every index records dependence. Removing one should require a mathematical reason.

This article was posted on Tue 14 April 2020. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.