Purchase Solution

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

Not what you're looking for?

Ask Custom Question

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

Attachments
Purchase this Solution
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.

Solution provided by:
Changping Wang, MA
Education
  • BSc , Wuhan Univ. China
  • MA, Shandong Univ.
Recent Feedback
  • "Your solution, looks excellent. I recognize things from previous chapters. I have seen the standard deviation formula you used to get 5.154. I do understand the Central Limit Theorem needs the sample size (n) to be greater than 30, we have 100. I do understand the sample mean(s) of the population will follow a normal distribution, and that CLT states the sample mean of population is the population (mean), we have 143.74. But when and WHY do we use the standard deviation formula where you got 5.154. WHEN & Why use standard deviation of the sample mean. I don't understand, why don't we simply use the "100" I understand that standard deviation is the square root of variance. I do understand that the variance is the square of the differences of each sample data value minus the mean. But somehow, why not use 100, why use standard deviation of sample mean? Please help explain."
  • "excellent work"
  • "Thank you so much for all of your help!!! I will be posting another assignment. Please let me know (once posted), if the credits I'm offering is enough or you ! Thanks again!"
  • "Thank you"
  • "Thank you very much for your valuable time and assistance!"
Purchase this Solution
Free BrainMass Quizzes
Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Probability Quiz

Some questions on probability

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

View More Free Quizzes
Related BrainMass Solutions

  • Show that every tree is central or bicentral.

    Show that every tree is central or bicentral. ( Kn is call complete graph and it if every two of its vertices are adjacent and every vertex has degree n) 2.- Prove taht a tree with Delta(T)=k ( Delta means maximum degree) has at least k vertices of

  • Temperature at Equilibrium

    Now manipulating the formula T will be equal to delta H over (delta S - RTlnKeq). Assume that delta S and delta H do not change much with temperature.

  • From Hot to Cool: The Second Law of Thermodynamics

    Heat absorbed by water when ice completely melts = mL = 10^-3*3.34*10^5 = 334 J Now: 334 = 1*4187*(20-t) Therefore, t = 19.92 degree C Since this is so close to 20 degree C, we can take the temperature of the system to be constant at 20 degree C throughut

  • Self-complementary graph proof

    98574 Self-Complementary Graph Proof 1.10 Let G be a self-complementary graph of order n, where n=1(mod 4) Prove that G contains at least one vertex of degree (n-1)/2 (hint: Prove the stronger result that G contains an odd number of vertices of degree

  • Relations and Graph Theory.

    Solution: No, any binary tree T with height 4 has at most 24 = 16 terminal vertices, so such a tree cannot have 17 terminal vertices. 16. How many vertices does a complete binary tree of height h have? Prove it.

  • Trees

    If T is a tree with 50 vertices, the largest degree that any vertex can have is 49. -------------------------------------------------------- a. If T is a rooted binary tree of height 5, then T has at most 25 leaves.

  • Forest and subgraph

    Pick any vertex and follow an edge out of it. The vertex that you go to has degree at least two (since there are no vertices of degree 1), so we can follow another edge out of it.

  • Graphing with Vertices

    Suppose T is a tree with n vertices, an every vertex has degree 4 or is a leaf. How many leaves does T have? 10. Find the clique number an independence number of the following graph.

  • Graphs, Digraphs, Trees and Forests

    It is a collection of trees. Now we know that every tree has at least two vertices of degree 1. So if there is any edge, we have at least 2 vertices of degree 1. If not we have at least vertex of degree 0.

View More Related Solutions