What is the number of trees? tagged trees

Question

Question: what is the number of trees T(V,E) on the set $({v_1,v_2,v_3,v_4,v_5,v_6,v_7,v_8})$ that have at least two vertices with a 3 degree.

edit: would like if someone can confirm I did it right:

total number of trees: $8^6 - \frac{8!}{2} - \frac{6!}{2} * 8 * 7 = 221824 $

Thanks in advance!

Answer 1

There are quite a number of other shapes of tree that meet your requirement. I don't know an easy of finding them. You just need to carefully draw them. For the tree you show there are only three equivalent vertices-the leaves coming off the four vertex. The other two leaves are distinguishable by their positions in the tree, so the number of ways to label it is $\frac {8!}{3!}=6720$

Answer 2

Assuming that the high-degree vertices have degree at least $3$, there are several possible pictures (not just this one). I think it's easier to do complementary counting. Cayley's formula tells us that there are $8^6$ labeled trees total, so all we need to do is find the number of labeled trees with at most one high-degree vertex, and subtract it from $8^6$.

(This helps not just because there's fewer cases, but because the cases are simpler.)

If no vertex has degree more than $2$, then we have a path. There are $\frac{8!}{2}$ ways to label the vertices (dividing by $2$ to account for the fact that we can look at the path from two ends).

If there is only one vertex of high degree, the graph we get is called a "spider", because graph theorists are weird. There's a central vertex, and several paths radiating out from it. The total length of the paths is $7$, so we have several cases to consider, but each of them is fairly simple: for example, if we have a path of length $3$ and four paths of length $1$, we can label the vertices in $8!$ ways, but the four paths of length $1$ are identical and can be rearranged in $4!$ ways, for $\frac{8!}{4!}$ distinct labelings.

You have some casework to do for the spiders, but this should be enough to get you started.