1
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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).

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.