Ask Question
17 March, 10:27

Prove that every tree has at least two vertices of degree 1

+5
Answers (1)
  1. 17 March, 10:45
    0
    A tree must be connected by definition. This means that there can be no vertices of degree 0 in a tree. Assume for contradiction that we have v vertices and that v - 1 have degree at least degree two. Then we know that the sum of the degrees of the vertices is at least 1 + 2 (v-1) which is equal to 2v - 1. Therefore we know that the number of edges must be at least v - 1/2. But this is impossible because a tree must have exactly v - 1 edges. Thus we have shown by contradiction that every tree has at least two vertices.
Know the Answer?
Not Sure About the Answer?
Find an answer to your question 👍 “Prove that every tree has at least two vertices of degree 1 ...” in 📗 Mathematics if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers