Understanding how to count the degree of the vertices


Problems:

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

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

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 Δ(T) = k and there are s vertices of degree 1, where sv∈V(G) = 2|E(G)|, we know that

                  2|E(T)|=Σv∈V(T)d(v)>2[|V(T)|-s-1]+s+k

Note: To count Σv∈V(T)d(v),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

                     Σv∈V(T)d(v)>2[|V(T)|-s-1]+s+k

(Why happened this I don't understand this inequality can you explain this better, can you make a graph)

So,

                2|E(T)|=2|V(T)|-s-2+k=2|v(T)|-1+(K-S-1)

As s>0 Hence,

                2|E(T)|=2|V(T)|-1+(k-s-1)>2|V(T)|-1

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

Solution Preview :

Prepared by a verified Expert
Mathematics: Understanding how to count the degree of the vertices
Reference No:- TGS01939044

Now Priced at $20 (50% Discount)

Recommended (92%)

Rated (4.4/5)