This is a practice question from the text.

The Question : Show that a tree with two vertices of degree $3$ must have at least four vertices of degree $1$. I have the answer to PART A.

Part B) Show that the result of Part (a) is the best possible i.e. a tree with two vertices of degree $3$ need not have five vertices of degree $1$.

I would really appreciate a hint that could help me solve part B.


For Part B, consider this tree: >-<

  • $\begingroup$ thanks for the reply. So should my proof be that the tree >-< is the simplest form of a tree with two vertices of degree 3 and it clearly has 4 vertices of deg 1. $\endgroup$ – Kj Tada Jun 5 '13 at 23:33
  • $\begingroup$ You only need one example to show (a) is best possible, and this does the trick. Others will too, e.g. >----< $\endgroup$ – vadim123 Jun 5 '13 at 23:34
  • $\begingroup$ thankyou again, that is very intuitive however is there a way to prove that the result in Part a is the best possible. As just sketching the graph >-< only shows that result of Part a is possible but not the best possible. I could be over thinking this. $\endgroup$ – Kj Tada Jun 5 '13 at 23:39
  • $\begingroup$ I think your difficulty stems from understanding what it means that "the result in Part a is the best possible". You have proved a lower bound on something (namely, the number of vertices of degree 1 in a tree with two vertices of degree 3 is at least 4). If this were not the best possible, that means that there would be a better lower bound, i.e. a higher lower bound. A higher lower bound would be at least 5. But 5 can not be a lower bound: >-< is a counterexample. $\endgroup$ – Mees de Vries Jun 6 '13 at 0:02
  • $\begingroup$ Thank you you were right I was having a hard time understanding the fact that it is best possible and your explanation helped. Thanks vadmin123 and Mees de Vries $\endgroup$ – Kj Tada Jun 6 '13 at 0:24

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.