102k views
3 votes
Show That If T Is A Tree, Then T Contains At Least Δ(T) Leaves.

User Jeremija
by
7.6k points

1 Answer

0 votes

Final answer:

A tree contains at least Δ(T) leaves

Step-by-step explanation:

A tree is a connected graph with no cycles. The degree of a vertex in a tree represents the number of edges incident to that vertex. The maximum degree of any vertex in a tree is denoted by Δ(T).

To show that if T is a tree, then T contains at least Δ(T) leaves, we can use the fact that in any connected graph, the number of edges is one less than the number of vertices.

Let's assume that T contains less than Δ(T) leaves. In that case, the sum of the degrees of all vertices in T would be less than 2*(Δ(T)). However, the sum of the degrees of all vertices in T is always equal to 2 times the number of edges in T. Since T is a tree, it has (n-1) edges, where n is the number of vertices. Therefore, we have a contradiction. Hence, T must contain at least Δ(T) leaves.

User GaspardP
by
7.9k points

No related questions found

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.