(Graph Theory)
Let G be a tree, and let k be the number of vertices in G whose degree is at least 3. Prove that G has at least k+2 leaves.
Use this theorem: "In any graph, the sum of the degrees of the vertices is equal to twice the number of edges."

I need a formal mathematical proof. I have figured out ways to prove it that I could explain in sentences, but they don't utilize this theorem and are somewhat unmathematical.

Question

(Graph Theory)
Let G be a tree, and let k be the number of vertices in G whose degree is at least 3. Prove that G has at least k+2 leaves.
Use this theorem: "In any graph, the sum of the degrees of the vertices is equal to twice the number of edges."

I need a formal mathematical proof. I have figured out ways to prove it that I could explain in sentences, but they don't utilize this theorem and are somewhat unmathematical.

anonymous · Answer

you might try to ask same question in math group