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?
Best Answer
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$