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 statement for the number of trees on $n$ vertices given by Cayley's formula: $n^{n-2}$. But if we didn't know about this, we could go about it in the following way:
Remember that on $4$ vertices, every tree must have $3$ edges. There are two options: if the tree is not a path, then there's a vertex of degree $3$ (can't be more) that accounts for all edges. So the graph must be $P_4$ or $K_{1,3}$.
For $K_{1,3}$, we have $4$ choices for the central vertex: then all other choices are forced. For $P_4$, we have $\left( \begin{array}{c} 4 \\ 2 \end{array} \right)$ choices for the central vertices (we simply choose any two out of $4$ labeled vertices), and then two ways to connect the two remaining leaves, so $12$ choices altogether.
This gives us $16$ distinct trees ($2$ up to isomorphism).