# Find a tree with a given sequence and show that all such trees have the same number of vertices

Find a tree with degree sequence $(4,3,3,3,2,2,2,1,\ldots),$ where the number of vertices of degree $1$ is not specified and prove that any tree found must have the same number of vertices.

One possible tree is as follows. First consider the simple path $ABCDE.$ Then at the vertex $E,$ the tree will have three edges $EF, \ EG, \ EH.$ At the vertex $F,$ there are two edges $FI, \ FJ.$ Also, the vertex $G$ splits into $GK, \ GL.$ Finally, there are edges $HM, \ HN$ at the vertex $H.$

Assuming the tree above is correctly constructed and given $(4,3,3,3,2,2,2,1,\ldots),$ looks like the actual degree sequence must be $(4,3,3,3,2,2,2,1).$ Seems to me all the trees constructed from the sequence $(4,3,3,3,2,2,2,1)$ must have $8$ vertices.

Does the above make sense?

• Does this make sense? I would say no, as finite trees have at least two leaves. – Theo Bendit Jul 18 '17 at 17:32
• @TheoBendit, I think the endpoints of $FI, \ FJ, \ GK, \ GL, HM, \ HL$ are the leaves. There are $6$ leaves. – user464381 Jul 18 '17 at 17:43

For a tree, the number of vertices $V$ equals the number of edges $E$ plus 1.

The number of edges $E$ is the sum of all the degrees divided by 2.

We know there are $7+n$ vertices, with $n$ the number of vertices with degree $1$ (the leaves)

We also know that the sum of the degrees is $19+n$ ($4+3+3+3+2+2+2=19$)

Hence:

$7+n = \frac{19+n}{2}+1$

So: $12 +2n = 19+n$

Hence, $n=7$, and total number of vertices is $14$

• @ Bram28, nice. Does that mean all the trees constructed according to the givens have $14$ vertices? – user464381 Jul 18 '17 at 17:57
• @user464381 Yes, I proved that there have to be $7$ leaves, i.e. $7$ vertices with degree $1$, and hence there have to be exactly $14$ vertices. – Bram28 Jul 18 '17 at 18:03
• @ Bram28, I now see I constructed a right tree. Just read the degree sequence off of it incorrectly. The nodes $A, \ FI, \ FJ, \ GK, \ GL, HM, \ HL$ are all of degree one. Thank you very much. – user464381 Jul 18 '17 at 18:16
• @user464381 Right, and so your tree has degree sequence $(4,3,3,3,2,2,2,1,1,1,1,1,1,1)$ instead of $(4,3,3,3,2,2,2,1)$, and so your tree has indeed $14$ vertices instead of $8$. But, in your post you only showed that this particular one tree would have $14$ vertices ... you did not show that any tree would have to have $14$ vertices. For that, you'll need something akin to what I did. – Bram28 Jul 18 '17 at 18:20