1
$\begingroup$

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?

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

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$

$\endgroup$
  • $\begingroup$ @ Bram28, nice. Does that mean all the trees constructed according to the givens have $14$ vertices? $\endgroup$ – user464381 Jul 18 '17 at 17:57
  • $\begingroup$ @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. $\endgroup$ – Bram28 Jul 18 '17 at 18:03
  • $\begingroup$ @ 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. $\endgroup$ – user464381 Jul 18 '17 at 18:16
  • $\begingroup$ @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. $\endgroup$ – Bram28 Jul 18 '17 at 18:20

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.