1.
{{1, 5}, {2, 6}, {2, 11}, {3, 10}, {4, 9}, {4, 13}, {5, 11}, {6, 7}, {6, 10}, {7, 13}, {8, 12}, {8, 14}, {11, 12}}
[5, 10, 11, 4, 13, 6, 7, 6, 2, 11, 12, 8]


2.
[5, 10, 11, 2, 2, 4, 8, 11, 3, 9, 10, 13, 12, 13, 14]
{{1, 5}, {2, 4}, {2, 5}, {2, 10}, {3, 9}, {3, 11}, {4, 6}, {7, 8}, {8, 11}, {9, 10}, {10, 13}, {12, 13}, {13, 14}, {14, 15}}, [11, 12]


3.
RandTree(100);
InvPruffer(Pruffer(%));
InvPruffer(Pruffer(T))=T is true


4.

RandTree1:= proc(n):
 InvPruffer(RandF(n-2)):
end:

time(RandTree(2000)) = 0.359
time(RandTree1(2000)) = 1.750

RandTree1 calls InvPruffer which runs a double for loop (once in itself and once in the function mex called inside the loop, while RandTree only runs a single for loop.


5. 

EstAveLeaves:= proc(n,K) local i,sum:
sum:=0:
for i from 1 to K do
  sum:=sum + nops(Leaves(RandTree(n))):
od:
evalf(sum/K):
end:

EstAveLeaves(100,1000)=
37.33900000
37.36200000
37.39700000
99/exp(1)=36.42006468
pretty close, EstAveLeaves(100,1000) is closer to 37 while 99/exp(1) is closer to 36


6.

R:= proc(e,b):
sum(numbcomb(e,s)*b^s*R(e-s,s) ,s=1..e):
end: