How to count the number of cubic tree-level Feynman diagrams at $n$ points?

To obtain a diagram with $n$ external legs from a diagram with $n-1$ external legs, you can insert the external leg labelled $n$ into any of the $2n-5$ edges. That there are $2n-5$ edges in a diagram with $n-1$ external legs follows by induction, since there are $3$ edges in a diagram with $3$ external legs and the insertion of another external leg increases the number of edges by two.

You might want to try posting such questions on math.SE in the future, where a combinatorial question like this would most likely not have survived unanswered for two days.

User joriki has already provided a correct answer. Here we just add details and make some clarifying remarks.

I) Let $n\geq 3$ be an integer. Consider the set ${\cal T}(n)$ of connected trees with cubic vertices only and with $E_n=n$ external labelled lines with labels $1,\ldots, n$, and no labelling of internal lines and vertices. (We stress that loops are not allowed.) Clearly the number of vertices is $V_n=n\!-\!2$, and the number of internal lines is $I_n=n\!-\!3$, so the total number of lines is $$L_n~=~E_n+I_n~=~2n-3.\tag{1}$$ We want to prove by induction that $$|{\cal T}(n)|~=~(2n-5)!! \tag{2}$$ Obviously the formula holds for $n=3$ $$|{\cal T}(3)|~=~1.\tag{3}$$

II) Now let us consider the induction step. Consider a tree $T_{n-1}\in{\cal T}(n\!-\!1)$ with $L_{n-1}=2n-5$ lines. For each line

         |
         |
         |

in the tree $T_{n-1}$, we can add a vertex and an external line with the label $n$:

         |         
    n----|
         |

It is clear that the new tree $T_n$ belongs to ${\cal T}(n)$.

III) Conversely, if $n\geq 4$, and if we have a tree $T_n\in {\cal T}(n)$, we can by removing the external line with the label $n$ (and its neighboring vertex) obtain a tree $T_{n-1}\in{\cal T}(n\!-\!1)$. We conclude that

$$|{\cal T}(n)|~=~(2n-5) |{\cal T}(n\!-\!1)|.\tag{4} $$

The sought-for formula (2) follows.