Ask Question
29 June, 18:08

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

+1
Answers (1)
  1. 29 June, 20:18
    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?
Get an answer to your question ✅ “Prove that every tree has at least two vertices of degree 1 ...” in 📙 Mathematics if there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers