# Describe how are the trees with $n$ vertices that have the smallest and the largest possible number of vertices of degree 1.

Describe how are the trees with $$n$$ vertices that have the smallest and the largest possible number of vertices of degree 1.

Affirmation: The trees that have the least number of vertices of degree 1 are the path graphs. The graphs with the highest number of vertices of degree 1 are the star graphs. How can I show it?

• Those are the answers; were you also trying to prove these assertions? Specifically, if you ask a question it should include some actual question; I suggest you edit to make your question clear. if you are trying to prove these, you might find this question and the answers useful. Apr 10 at 20:28
• I am only asked to describe trees with these characteristics, and I would like to demonstrate my statements, but I don't know how. Apr 10 at 20:31
• What do you mean by "demonstrate" (or "show") in this context? Draw a picture? Do some calculation? Sorry if this is obvious to you but if I don't understand, I guarantee that others will also not understand. (And thanks for the question edit; that is an improvement) Apr 10 at 20:33
• Give an argument or explanation why my statements are correct... Apr 10 at 20:34
• The one with the most vertices of degree $1$ is the star (if all had degree $1$ then it wouldn't work). For the one with the least it is the path (it has only $2$, if there was less there would have to be as least $n$ edges). Apr 10 at 20:50

## 1 Answer

Your answer are correct, for the proof we'll need few facts.

I'll assume you know the handshaking lemma $$\sum_V d^°(v) = 2|E|$$ (the sum over all vertices of the degrees is two times the number of edges) ; and the characterization of trees with $$n$$ vertices as connected graphs with exactly $$n-1$$ edges

• there are no trees without degree one nodes

to prove this take a tree without degree one nodes, we first remark that no vertex can have degree $$0$$ (otherwise the graph is not connected, so it is not a tree), hence we assume all nodes have all degree at least $$2$$. Then we use the handshaking lemma: $$2|E| = \sum_V d^°(v) \leq \sum_V 2 = 2n$$, hence the graph would have at least $$n$$ edges, so it would not be a tree.

• there are no trees with only one degree one node

to prove this, we proceed by induction: from a tree $$T$$ with a single degree one vertex $$s$$, we construct a new tree $$T\setminus \{s\}$$ by deleting $$s$$. We get a tree with exactly one less vertex and one less edge. Since we only have a finite number of vertices, the induction stops at some point, and we end up with a tree without degree one vertex, which is impossible as we've just proved.

• there are no trees with $$n=|V|$$ degree one edges (other than the path with 2 vertex $$P_2$$)

here we also use the handshaking lemma: $$2|E| = \sum_V d^°(v) = |V| = n$$ so $$2(n-1)=n$$ hence $$n=2$$.

Now we have lower and upper bound that your examples match: the paths have exactly 2 degree one vertices and the stars have exactly $$n-1=|V|-1$$ degree one vertices.