Trees with vertex set I am having hard time understanding and solving the following question:  

There are exactly three trees with vertex set {1,2,3}. Note that all these trees are paths; the only difference is which vertex has degree 2. How many trees have a vertex set {1,2,3,4}?

So how I understand it is we have $K_3$ trees for the vertex set {1,2,3}. So since a tree is a path, we have a walk that repeats no vertex twice, or a path. When I drew it out, every time, only one vertex at a time has 2 degrees. (So far correct?) So what I don't understand is how we can determine the number of trees we can find for a vertex set $K_4$.

There is a general formula (which is not hard to prove) for a number of spanning trees of a graph as a determinant of submatrix of its Laplace/adjacency matrix. For $K_4$ it gives
$\det \begin{pmatrix}
3 & -1 & -1 \\
-1 & 3 & -1 & \\
-1 & -1 & 3
\end{pmatrix}=16.$
