I'm a bit surprised that this exercise appears so early in a combinatorics book without any hints.
Regarding your first question, yes, I understand the question the same way. What I don't understand is how you originally expected us to help you in interpreting the question without linking to your book or explaining what the "first row" was. I'd suggest to always directly link to any book you're referring to if it's available online, and also not to change the spelling if you quote from a book – I searched for the problem before you provided the link and would have found it if you hadn't changed the spelling of "labeled" to "labelled" :-)
Regarding your second question: What you want to count isn't the ways of labelling the vertices of a given graph; you want to count all such graphs with all labellings for all structures; so I don't think this approach will get you very far.
The problem itself doesn't define what exactly a rooted trivalent tree is. In particular, it's not immediately clear whether the root itself can have degree $1$ or $3$ or only one of the two. Unfortunately Google Books doesn't show (at least to me) the page with Figure 14.3 that the problem refers to, which would probably resolve this. However, this page seems to indicate that the root may be required to have degree $1$, which would fit with how this book seems to be use the term, and also with this solution, which apparently makes that assumption.
The given condition is equivalent to the condition that the vertices are labelled in decreasing order as viewed from the root. Thus we're counting the number of labelled full/proper/strictly binary trees with vertex labels increasing from the root.
The recurrence
$$a_n=\frac12\sum_{k=1}^{n-1}\binom{2n-2}{2k-1}a_na_{n-k}$$
derived in the solution linked to yields the initial terms $1,1,4,34,496,\dotsc$, which lead to OEIS sequence A002105.
The number of ways to fully parenthesize a string of $n$ letters, $C_{n-1}$, obeys the following recurrence:
$$
C_{n-1} = \sum_{i=1}^{n-1}C_{i-1}C_{n-i-1}
$$
To see this, consider the two "shallowest" groups in the parenthesization. Namely, ignoring the leftmost ( and the rightmost ), look at the parenthesis matching the leftmost (. This will surround the first $i$ letters in the string, which can be further paranthesized in $C_{i-1}$ ways, while the latter $n-i$ letters can be parenthesized in $C_{n-i-1}$ ways. For example when $n=5$, the $*$ illustrates all of the break points:
(1 * (2 (3 (4 5)))) C(0) * C(4) strings where the break point
(1 * (2 ((3 4) 5))) is after i=1
(1 * ((2 3) (4 5)))
(1 * ((2 (3 4)) 5))
(1 * (((2 3) 4) 5))
((1 2) * (3 (4 5))) C(1) * C(2) strings where the break point
((1 2) * ((3 4) 5)) is after i=2
((1 (2 3)) * (4 5)) C(2) * C(1) strings where the break point
(((1 2) 3) * (4 5)) is after i=3
((1 (2 (3 4))) * 5) C(4) * C(0) strings where the break point
((1 ((2 3) 4)) * 5) is after i=4
(((1 2) (3 4)) * 5)
(((1 (2 3)) 4) * 5)
((((1 2) 3) 4) * 5)
This recurrence gives you a quickly computable bijection from the first $C_{n-1}$ non-negative integers to binary trees. You are given an integer $k$ for which $0\le k\le C_{n-1}-1$. Compute the partial sums
$$
\sum_{i=1}^{s-1} C_{i-1}C_{n-i-1}
$$
to find the largest number $s\ge 1$ for which that partial sum is at most $k$. Then, insert parentheses into the list of numbers (1 2 3 ... n) as follows:
((1 2 ... s) (s+1 s+2 ... n))
If $s=1$, you can omit the parentheses around (1), and similarly when $s=n-1$ around (n).
Then, letting $$e=k - \Big(\sum_{i=1}^{s-1}C_{i-1}C_{n-i-1}\Big),$$ and letting \begin{align}k_1&=e\pmod {C_{s-1}}\\k_2&=\lfloor e/C_{s-1}\rfloor,\end{align} you will have $0\le k_1\le C_{s-1}-1$ and $0\le k_2\le C_{n-s-1}-1$, and you can recursively apply the bijections for $k_1$ to the list (1 2 ... s) and for $k_2$ to the list (s+1 s+2 ... n).
Edit: There was a "bug" in my bijection which I just fixed. You can test that it works here.
Edit2: I just fixed another off-by-one error.
Best Answer
The uniqueness of the prufer sequence comes from the fact that the trees are reconstructable.
For example, with $\{4,4,4,5\}$ The first number not in the code is $1$, so we attach vertex $1$ to $4$(the first entry in the code) now drop the $4$ from the code and add a $1$ to the back to get $\{4,4,5,1\}$.
The first number not in the code is $2$, so attach $2$ to $4$, drop the $4$ and add $2$ to the back to get $\{4,5,1,2\}$.
The first number not in the code is $3$, so attach $3$ to $4$, drop the $4$ and add $3$ to the back to get $\{5,1,2,3\}$
The first number not in the code is $4$, so attach $4$ to $5$, drop the $5$ and add $4$ to the back to get $\{1,2,3,4\}$.
Now we have exhausted the entire original code. The final step is to add an edge between the two numbers not shown in our new code, so attach $5$ to $6$.
This will give you back the original tree. Since we have a way to "Uncode" the prufer code, it is unique.