4. Prove by induction that if we are given n numbers d1, d2,...,dn so that E-I 2

Question

4. Prove by induction that if we are given n numbers d1, d2,...,dn so that E-I 2n 1 there is a tree T(V, E) with vertices v1, Un so that deg(vi) di. Hint: Remove a number d, of value 1 (it exists. See above). After the removal use the fact that there is a number di that is at least 2. Change di to di -1. Apply the induction hypothesis, on the n - 1 new numbers (there are n - 1 numbers since we remove a number of value 1 from the set of numbers). The number 1 that we removed needs to be a leaf (to have degree 1) because di 1. The last step is adding back a leaf. But recall that the degree of di is di-l in the induction tree.

Explanation / Answer

For n = 1, this is trivial. Suppose the claim holds for n ? 1 and let T be a tree with n vertices where n ? 2. Let v be a leaf of T and let e be the unique edge containing v. Then note that the graph T 0 obtained by deleting v and e from T remains connected and clearly has no cycles as T has none. Thus T 0 is also a tree. Now the inductive hypothesis kicks in and says that T 0 has (n ? 1) ? 1 = n ? 2 edges. Since T 0 contains all the edges of T except e, we see that T has n ? 1 edges.

For the “if” part, we also employ induction. The statement is not quite true for n = 1 (the degree sequence will not have positive integers in it), so we deal with n = 2 as the base case. Here the only sequence of positive integers d1, d2 with d1 + d2 = 2 is 1, 1 and yes, there is a tree with that degree sequence, namely a single edge connecting two vertices. Now assume n ? 3 and let d1, . . . , dn be a sequence of positive integers such that Pn i=1 di = 2(n?1). We claim that dj = 1 for some j. Otherwise, being positive integers every di is larger than 2 and we get 2(n ? 1) = Xn i=1 di ? Xn i=1 2 = 2n , a contradiction. We may assume j = 1 so d1 = 1, by relabeling the vertices. Similarly, we observe that dk ? 2 for some k: Otherwise 2(n ? 1) = Pn i=1 di = n, so n = 2, contradicting n ? 3. Again by relabeling, we may assume d2 ? 2.

Now since (d2 ? 1) + Xn i=3 di = Xn i=1 di ! ? 2 = 2(n ? 1) ? 2 = 2(n ? 2), by the induction hypothesis there exists a tree whose degree sequence is the sequence of positive integers d2 ? 1, d3, . . . , dn. Attaching a single edge to the vertex with degree d2 ? 1, we get a tree with a degree sequence 1, d2, . . . , dn.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.