Number of trees $T = (V,E) \;$ such that $V = \left \{ 1,2,3,4,5,6,7 \right \} \;$, $\deg(1) = 2$ , $\deg(t)<5 \;\forall\; 2\leq t\leq 7$

Question

I tried summing all of the cases (I found 4), but somehow i'm getting the wrong answer.

For ex. the number of trees on 7 vertices such that the following sequence is the sequence of their degrees:

My solution (wrong) using Cayley's formula:

The only possible degree sequences are:

$(2,1,1,2,2,2,2) = \binom{5}{1}*\binom{6}{4}$

$(2,3,2,2,1,1,1) = \binom{5}{2}*6\binom{5}{2}$

$(2,3,3,1,1,1,1) = \binom{5}{2,2}*\binom{6}{2}$

$(2,4,2,1,1,1,1) = \binom{5}{3}*6*4$

What am I missing here?

Answer 1

Since all degrees $\le 2$, the tree is actually a path. The two vertices of degree $1$ have to go on the ends: wlog $2$ on the left and $3$ on the right, and the other five can be in any order. So $5! = 120$ such trees.

Answer 2

The unlabelled trees with $7$ vertices are We have to rule out the last three which have a vertex of degree $\geq 5$ or no vertex of degree $2$.

So for each of the $8$ cases we compute the number of labelled trees such that $\deg(1) = 2$ and $\deg(t)<5 \;\forall\; 2\leq t\leq 7$ and we add them all together: $$5\cdot \frac{6!}{2}+3\cdot\frac{6!}{2}+3\cdot 6!+3\cdot\frac{6!}{3!}+1\cdot \frac{6!}{2^3}+1\cdot\frac{6!}{2}+2\cdot\frac{ 6!}{3!}+2\cdot\frac{6!}{2^2}=6450.$$ Each term is obtained as the number of vertices of degree $2$ (positions for the vertex $1$) multiplied by $6!$ (for arranging the remaining $6$ vertices) and finally divided by the number of symmetries.

Answer 3

In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.

If $\deg(1)=2$, then we have $\binom{6}{2}=15$ ways of constructing/building the tree:

Each possibility could be extended to a tree. Look at the $6$ vertices $v \in V'=\{2,3,4,5,6,7\}$. Two of them (doesn't matter which two in particular) are already connected with vertex $1$, these $v$ should have $\deg(v)<4 \Leftrightarrow \deg(v)\in\{1,2,3\}$. Four of them should have $\deg(v)<5 \Leftrightarrow \deg(v)\in\{1,2,3,4\}$.

So, the degree sequence of the vertices $(1,2,3,4,5,6,7)$ would be $(2,b,c,d,e,f,g)$ with $1\leq b,c \leq 3$ and $1 \leq d,e,f,g, \leq 4$. Because we have $3^2\cdot4^4 =2304$ possible combinations for this degree sequence, there could be $2304$ possible trees, but for example a degree sequence like $(2,2,2,2,2,2,2)$

(and some more) wouldn't be a tree, because this would contain cycles and a tree is defined to be acyclic or without cycles...

Answer 4

You have one vertex of degree $2$ and there must be two pendant vertices. So you have four vertices left whose sum of degrees need to be $8$. Given the restrictions placed on the degrees, the only possible degrees of these vertices are $(2, 2, 2, 2)$, $(3, 2, 2, 1)$, $(3, 3, 1, 1)$ and $(4, 2, 1, 1)$. This gives the possible degree sequences as

• $(2, 2, 2, 2, 2, 1, 1)$
• $(3, 2, 2, 2, 1, 1, 1)$
• $(3, 3, 2, 1, 1, 1, 1)$
• $(4, 2, 2, 1, 1, 1, 1)$

Now you will have to do some drawing to find that there is only one tree with first sequence, three trees with second sequence, and two trees each with third and fourth degree sequence. These are trees drawn in RobertZ answer.