[26] Show that almost every labeled tree on n nodes has maximum degree of O(log n/ log log n).

Comments. Hint: represent a labeled tree by a binary sequence of length

(n − 2) log n (the Pr¨ufer code). Prove a one-to-one correspondence between labeled trees and binary sequences of such length. Use incompressibility to show that if a tree has larger degree, then one can compress the corresponding binary sequence. Since most binary sequences cannot be compressed, most trees do not have larger degree. Source: [W.W.

Kirchherr, Inform. Process. Lett., 41(1992), 125–130].