Trees [4 marks) (f) Let m 2 2 and let T be an m-ary rooted tree of height h 2 0.

Question

Trees

[4 marks) (f) Let m 2 2 and let T be an m-ary rooted tree of height h 2 0. Show that T contains at [4 marks) (g) Let m 2 2 and h 2 0. Construct an m-ary rooted tree of height h which contains precisely [4 marks) (h) Let G = (V,E) be a connected graph and let e E. Show that e is contained in every [6 marks] (e) Show that a connected graph with n vertices and n -1 edges is a tree m'· ' most 1 vertices. n- mh+1 vertices. (This shows that the bound in (f) is best possible.) spanning tree of G if and only if G, (V, E {e)) is disconnected

Explanation / Answer

(e)-

Induction Step: Let n be a positive integer and suppose any connected graph with k vertices has at least k 1 edges for any integer k with 1 k n. Let G be a connected graph with n + 1 vertices and let v be a vertex of G. Remove v and all incident edges to v from G. The resulting graph, which we will call G', may or may not be connected, but we do know it has n vertices. Suppose G' has s components where 1 s n. Each component is a connected graph with n or fewer vertices, so we may apply the induction hypothesis to each component. For each component, if the component has k vertices then it has at least k 1 edges. Thus G' must have at least n s edges. When v was removed from G we only removed edges incident to v to obtain G'. For each component in G' there must be an edge from v to a vertex in that component since G was connected. Thus there must be at least s more edges in G than there are in G', i.e. the number of edges in G is at least (n s) + s = n

(h)-

Suppose G is a tree. Then by defintion, G is connected. Let {u, v} be an arbitrary edge in G. Then {u, v} is clearly a path from u to v. Since G is a tree this is the only path in G between u and v, so if the edge {u, v} is removed from G there will be no path from u to v in the resulting graph. Thus the resulting graph is disconnected. Conversely, suppose G is connected but the removal of any edge in G produces a disconnected graph. We need to prove G is a tree. We already have G is connected, so what we still need to show is that G is acyclic. We use contradiction. Suppose G contains a cycle, C, and {u, v} is an edge in C. If we remove this edge we claim the resulting graph, say G' , is still connected. Let w and x be vertices in G' . Since G is connected there is a path from w to x in G. If this path uses the edge {u, v}, then we can replace this edge in the path with the part of the cycle left from C after removing {u, v}. The new path is a path from w to x that does not use {u, v}, so it is a path in G' . If the original path does not use {u, v} then it is a path in G'. Thus there is a path in G' from w to x. since these vertices were arbitrary we have shown G' is connected. This contradicts our assumption that the removal of any edge in G produces a disconnected graph

(f) & (g) use A full m-ary tree with i internal vertices has n = mi + 1 vertices & An m-ary tree with height h has at most m^h leaves.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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