1. Show that for any unlabeled tree, there is a labeling such that x_i=i for i=1, ..., n-1 in the Prüfer construction.

2. Show that given 1 ≤ y_i ≤ n for i=1, ..., n-2, there is an O(n) algorithm to construct the sequence x_i=i, for i=1, ..., n-1 in the Prüfer construction.