Ask Question
15 February, 21:29

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

+2
Answers (1)
  1. 16 February, 00:34
    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 you're in doubt about the correctness of the answers or there's no answer, then try to use the smart search and find answers to the similar questions.
Search for Other Answers