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?

  • $\begingroup$ 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. $\endgroup$ – Joffan Apr 10 at 20:28
  • $\begingroup$ I am only asked to describe trees with these characteristics, and I would like to demonstrate my statements, but I don't know how. $\endgroup$ – Kitty M. Apr 10 at 20:31
  • $\begingroup$ 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) $\endgroup$ – Joffan Apr 10 at 20:33
  • $\begingroup$ Give an argument or explanation why my statements are correct... $\endgroup$ – Kitty M. Apr 10 at 20:34
  • 1
    $\begingroup$ 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). $\endgroup$ – Onir Apr 10 at 20:50

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.


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.