Explore BrainMass
Share

Explore BrainMass

    Prove that a tree with Delta(T)=k (Delta means maximum degree) has at least k vertices of degree 1.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    I don't understand how you count the degree of the vertices.

    (See attached file for full problem description)

    ---
    2.- Prove that a tree with Delta(T)=k ( Delta means maximum degree) has at least k vertices of degree 1.

    Proof. We prove it by contradiction. Suppose that and there are s vertices of degree 1, where s<k. By a theorem , we know that

    Note: To count , we know that there is at least one vertex with maximum degree k; and there are s vertices with degree 1, so the rest of |V(T)|-s-1 vertices have degrees at least 2. Hence, we have
    (Why happened this I don't understand this inequality can you explain this better, can you make a graph)

    So,

    As s<k, we know that . Hence,

    which is a contradiction, since |E(T)|=|V(T)|-1 for tree T. We complete the proof

    © BrainMass Inc. brainmass.com October 9, 2019, 6:43 pm ad1c9bdddf
    https://brainmass.com/math/vector-calculus/prove-that-a-tree-with-delta-t-k-delta-means-maximum-degree-has-at-least-k-vertices-of-degree-1-95966

    Attachments

    Solution Summary

    This solution is comprised of a detailed explanation to prove that a tree with Delta(T)=k (Delta means maximum degree) has at least k vertices of degree 1.

    $2.19