Basic Examples (2) 

The labeled tree associated with a Prüfer code:

In[1]:=

Out[1]=

Do not show labels:

In[2]:=

Out[2]=

Applications (2) 

Generate a random tree on n vertices:

In[3]:=

In[4]:=

Out[4]=

Count distinct unlabeled trees on n vertices:

In[5]:=

In[6]:=

Out[6]=

In[7]:=

Out[7]=

Properties and Relations (7) 

The tree associated with a Prüfer code of length n has n+2 vertices:

In[8]:=

Out[8]=

There are n^n-2 tuples of length n−2 on the labels 1 to n and, correspondingly, the same number of different labeled trees:

In[9]:=

In[10]:=

Out[10]=

In[11]:=

Out[11]=

In[12]:=

Out[12]=

Empty Prüfer code corresponds to a tree with only two leaves:

In[13]:=

Out[13]=

The resource function LabeledTreeToPruferCode can be used to get the Prüfer code of a labeled tree:

In[14]:=

Out[14]=

In[15]:=

Out[15]=

PruferCodeToLabeledTree reconstructs the tree:

In[16]:=

Out[16]=

Composition of the resource function LabeledTreeToPruferCode and PruferCodeToLabeledTree is an identity operation for any valid value of Prüfer's code:

In[17]:=

In[18]:=

Out[18]=

In[19]:=

Out[19]=

In[20]:=

Out[20]=

The Prüfer code of a path is a sequence of n-2 distinct integers:

In[21]:=

In[22]:=

Out[22]=

A sequence of n-1 copies of k is the Prüfer code for an n-pointed star with the center vertex k:

In[23]:=

Out[23]=

Properties and Relations (2) 

Integer inputs are also accepted:

In[24]:=

Out[24]=

The result is equivalent to using the digits of the integer:

In[25]:=

Out[25]=