$3.$ Random Trees

The nx$.$random$\_$tree$($n$)$ command can be used to generate a random tree on the n vertices represented in python by range$($n$)($in order$).$

Such a tree can be converted into a sequence of n$2$

numbers, its Pr$$fer code by the python function pruefer$\_$code, defined as follows:

def pruefer$\_$node$($tree$)$:

for x in tree:

if tree.degree$($x$)==1$:

for y in tree$[$x$]$:

tree.remove$\_$node$($x$)$

return y

def pruefer$\_$code$($T$)$:

tree $=$ T$.$copy$()$

return $[$pruefer$\_$node$($tree$)$ for k in range$($tree$.$order$()-2)]$

T $=$ nx$.$random$\_$tree$(12)$

code $=$ pruefer$\_$code$($T$)$

code

Conver

def tree$\_$pruefer$($code$)$:

# initialize graph and defects

n $=$ len$($code$)+2$

tree $=$ nx$.$empty$\_$graph$($n$)$

degrees $=[1$ for x in tree$]$

for y in code:

degrees$[$y$]+=1$

# add edges

for y in code:

for x in tree:

if degrees$[$x$]==1$:

tree.add$\_$edge$($x$,$ y$)$

for z in $($x$,$ y$)$:

degrees$[$z$]-=1$

break

# final edge

e $=[$x for x in tree if degrees$[$x$]==1]$

tree.add$\_$edge$(*$e$)$

return tree

T$2=$ tree$\_$pruefer$($code$)$

Use, if needed, the above functions to experiment with random trees and$/$or sequences and answer the following:

$1.$ Which labelled tree on n nodes $\{0,1,...,$n$1\}$

corresponds to the Pr$$fer code $[0,1,2,...,$n$3]?($Note: you need to describe and justify mathematically an answer for all n$)$

$2.$More generally, what can one say about a tree T

whose Pr$$fer code consists of n$2$ distinct entries? $($Note: you need to describe and justify mathematically an answer for all n$.)$