215k views
4 votes
What is the size of the largest and smallest numbers of vertices of degree 1 possible in an n-vertex tree, for n > 2?

User Jlim
by
9.3k points

1 Answer

6 votes
Following the formula: Pn on n+1 vertices {v0, v1, v2, …, vn} With n>2 edges as vertices we know that the component is not a tree. At the same time we know it must contain a cycle. Therefore the size of the vertices is not possible to exceed 2n, and the degree of any vertex in any sub-graph has a minimal value of vn. Therefore the maxim is 2n and the minimum is vn.
User Stan Malcolm
by
7.9k points

No related questions found

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories