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