
	Home


	Homework Help


	Answer Board


	Resources (Beta)

You Are Here:

Member's Topic Headline:

Trees

Know the answer? Have a better solution? Share it.

Join the thousands of students
getting ahead in their classes.

Question:

mastan

Guru

Karma Points: 2,860

Date Posted: 7/25/2008 1:20:49 AM Status: Live

Asker's Rating: Lifesaver

Response:

We know that every tree with n vertices has n-1 edges.

Now, we have to show that there is a tree that has n vertices s.t

the degrees of the vertices d₁, d₂, ......., d_n.

We know for any graph, 2e = Σ _{v ε V} d(v).

then, 2e = d₁ + d₂ + .......... + d_{n .}

i.e 2e = 2n - 2 ( by the given condition )

∴ e = n -1.

∴ d₁, d₂, ......, d_n can be the degrees of vertices of a tree.

SamSan's Comment:

thank you

By reading or posting messages on these forums, you are agreeing to the Answer Board's Terms of Service and Conduct (TSC).