From Degrees to Prüfer Codes
A degree sequence specifies how many edges meet each labeled vertex, but it does not specify which vertices are joined. Prüfer codes provide a way to count all labeled trees that realize the sequence: each vertex appears in the code a number of times determined by its degree. The resulting count is a multinomial coefficient.
Throughout, a tree is a finite, simple, connected graph with no cycles, and its vertices have fixed, distinct labels. We consider a prescribed sequence \(d_1,\dots,d_n\) of positive integers, where \(d_i\) is the required degree of vertex \(i\). Trees are counted as different if their edge sets differ, even when they have the same degree sequence.
For \(n=2\), this code is the empty sequence. We use \(0!=1\). The earlier material on Prüfer codes establishes that encoding and decoding give a bijection between labeled trees on \(\{1,\dots,n\}\) and sequences of length \(n-2\) whose entries lie in \(\{1,\dots,n\}\). It also gives the degree rule: the degree of vertex \(i\) is one plus the number of times \(i\) occurs in the code. This rule follows from decoding: each occurrence of \(i\) makes a leaf adjacent to \(i\), and one final incident edge remains when the decoding ends.
The Prescribed-Degree Formula
Proof. First, every tree on \(n\) vertices has \(n-1\) edges. By the handshake lemma, the sum of its vertex degrees is twice its number of edges, hence \(2(n-1)\). Therefore, if the prescribed degrees do not sum to \(2(n-1)\), no tree realizes them.
Now suppose the sum condition holds. Set \(m_i=d_i-1\). Since each \(d_i\) is positive, each \(m_i\) is a nonnegative integer, and $$ \sum_{i=1}^n m_i=\sum_{i=1}^n(d_i-1)=2(n-1)-n=n-2. $$ By the degree rule for Prüfer codes, a tree has the prescribed degrees exactly when its code has \(m_i\) occurrences of label \(i\), for every \(i\). The number of sequences of length \(n-2\) with these symbol multiplicities is $$ \binom{n-2}{m_1,m_2,\dots,m_n} =\frac{(n-2)!}{m_1!m_2!\cdots m_n!} =\frac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}. $$ Indeed, choosing positions for each symbol gives this multinomial count; symbols with the same label are not distinguished from one another. By the Prüfer bijection, each such sequence decodes to exactly one labeled tree, and different sequences decode to different trees. Thus the count is the displayed formula. Since nonnegative multiplicities \(m_i\) with total \(n-2\) can be arranged into at least one sequence, the condition also guarantees that at least one such tree exists. \(\square\)
The positivity assumption matters. It rules out isolated vertices and ensures the problem concerns trees with every prescribed degree at least \(1\). For \(n=1\), the single-vertex tree has degree \(0\); it is a separate case and is not covered by the positive-degree formula.
Worked Counts and Decodings
Worked Example: Five Vertices with Three Degree-Two Vertices
Let the prescribed degrees on \(V=\{1,2,3,4,5\}\) be \(d_1,\dots,d_5=(1,1,2,2,2)\). Their sum is \(1+1+2+2+2=8\), and \(2(n-1)=2(5-1)=8\), so the condition holds.
The required Prüfer-code multiplicities are \(d_i-1\), namely \((0,0,1,1,1)\). The code has length \(5-2=3\), so it must contain \(3,4,5\) once each. The number of possible codes is $$ \frac{3!}{0!0!1!1!1!}=\frac{6}{1}=6. $$ They are \(345,354,435,453,534,543\). The bijection shows that these give six different trees, all with the required degrees.
For a direct check of one code, decode \(345\). Initially, the labels absent from the code are \(1,2\); the smallest is \(1\), so add edge \(13\) and remove \(1\). The remaining code is \(45\), and the active labels are \(2,3,4,5\). The absent labels are \(2,3\), so add \(24\) and remove \(2\). The remaining code is \(5\), and the active labels are \(3,4,5\); the absent labels are \(3,4\), so add \(35\) and remove \(3\). Join the two remaining labels \(4,5\), adding \(45\).
The decoded edge set is \(\{13,24,35,45\}\). Its degrees are \(1,1,2,2,2\), as prescribed. There are four edges on five vertices, as a tree must have. The six-code count is independently confirmed by arranging three distinct symbols in three positions: \(3\cdot2\cdot1=6\).
Worked Example: A Repeated Prüfer Symbol
Let \(V=\{1,2,3,4,5,6\}\) and prescribe degrees \((1,1,1,2,2,3)\). Their sum is \(1+1+1+2+2+3=10\), which equals \(2(6-1)=10\).
The multiplicities \(d_i-1\) are \((0,0,0,1,1,2)\). Thus the code has length \(4\), with one \(4\), one \(5\), and two \(6\)s. The number of codes, and hence of trees, is $$ \frac{4!}{0!0!0!1!1!2!}=\frac{24}{2}=12. $$ Equivalently, choose the position of \(4\) in \(4\) ways and then the position of \(5\) in \(3\) ways; the remaining two positions contain \(6\). This gives \(4\cdot3=12\), independently confirming the count.
Decode the particular code \(6465\). Initially, \(1,2,3\) are absent, so delete the smallest, \(1\), and add \(16\). In the remaining code \(465\), the active labels are \(2,3,4,5,6\); the absent labels are \(2,3\), so delete \(2\) and add \(24\). In the remaining code \(65\), the active labels are \(3,4,5,6\); the absent labels are \(3,4\), so delete \(3\) and add \(36\). In the remaining code \(5\), the active labels are \(4,5,6\); the absent labels are \(4,6\), so delete \(4\) and add \(45\). Finally, add \(56\).
The edge set is \(\{16,24,36,45,56\}\). Its degrees are \(1,1,1,2,2,3\): vertices \(1,2,3\) each occur in one edge, vertices \(4,5\) each occur in two, and vertex \(6\) occurs in three. The edge count is \(5=6-1\), also as required for a tree.
Worked Example: Two Trees with the Same Degree Sequence
On \(V=\{1,2,3,4\}\), prescribe degrees \((1,1,2,2)\). The sum is \(1+1+2+2=6=2(4-1)\). The multiplicities are \((0,0,1,1)\), so the code has length \(2\), containing \(3\) and \(4\) once each. There are $$ \frac{2!}{0!0!1!1!}=\frac{2}{1}=2 $$ codes: \(34\) and \(43\).
Decode \(34\): the smallest label absent from the code is \(1\), giving edge \(13\). In the remaining code \(4\), the active labels are \(2,3,4\); the absent labels are \(2,3\), so add \(24\). The final edge is \(34\). The resulting edge set \(\{13,24,34\}\) has degrees \((1,1,2,2)\).
Decode \(43\): first add \(14\), since \(1\) is the smallest absent label. The remaining code is \(3\), and among the active labels \(2,3,4\), the smallest absent label is \(2\); add \(23\). The final edge is \(34\). This gives \(\{14,23,34\}\), again with degrees \((1,1,2,2)\). The two edge sets differ, so they are distinct trees. Both have three edges, and the two possible codes account for the full count.
How to Apply the Formula
For a given sequence, first check that there are \(n\ge2\) positive entries and that their sum is \(2(n-1)\). Then subtract \(1\) from each degree to obtain the symbol multiplicities. The multiplicities must be nonnegative and sum to \(n-2\); under the stated conditions, this follows from the calculation in the proof. Finally, count arrangements of those symbols, dividing by the factorial of each multiplicity because copies of the same label are indistinguishable.
The formula gives a count for a fixed assignment of degrees to labels. If the values are rearranged among labels, that is a different prescribed assignment and may describe a different set of trees. The factorial denominator accounts only for repeated occurrences of a symbol in one code; it does not identify trees obtained by relabeling vertices.
Common Pitfall: Use \(d_i-1\), Not \(d_i\)
A frequent error is to use \(d_i\) as the number of times label \(i\) appears in the code. The code has length \(n-2\), not the sum of the degrees. For the sequence \((1,1,2,2)\), using the degrees as multiplicities would demand \(1+1+2+2=6\) symbols in a code of length \(2\). Even inserting those values into a mistaken factorial expression gives \(2!/(1!1!2!2!)=1/2\), which cannot be a number of trees.
The correction is to use \(d_i-1\). The multiplicities become \((0,0,1,1)\), which sum to \(2\), and the correct count is \(2!/(0!0!1!1!)=2\). The subtraction by one reflects the final incident edge that each vertex receives in the decoding process in addition to its occurrences as a code symbol.
This count refines the total count of labeled trees by separating trees according to their degree sequences. It is useful whenever the degree of each labeled vertex is specified, rather than merely the number of vertices. The essential translation is concise: prescribed degree \(d_i\) means prescribed Prüfer multiplicity \(d_i-1\).
Check Your Understanding
For each question, keep the labels fixed and count trees with different edge sets as different.
- How many labeled trees on \(\{1,2,3,4,5\}\) have degrees \((1,1,1,2,3)\)? Check the degree sum before applying the formula.
- Explain why a positive sequence of length \(n\) whose entries sum to \(2(n-1)\) determines nonnegative Prüfer multiplicities totaling \(n-2\).
- How many labeled trees on \(\{1,2,3,4,5,6\}\) have degrees \((1,1,2,2,2,2)\)? State the symbol multiplicities.
- Why does the formula not apply to the one-vertex tree, and what is that tree's degree?
- For degrees \((1,1,2,2)\), decode both possible Prüfer codes and verify the degree sequence of each resulting tree.