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

Question

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. h+1-1 most m1 vertices. mh+1-1 vrtces. (This shows that the bound in (f) is best possible.) 1S m spanning tree of G if and only if G, (V, E {e) is disconnected

Explanation / Answer

Let G be a connected graph with n vertices and n 1 edges. We show that G contains no cycles. Assume to the contrary that G contains cycles. Remove an edge from a cycle so that the resulting graph is again connected. Continue this process of removing one edge from one cycle at a time till the resulting graph H is a tree. As H has n vertices, so number of edges in H is n1. Now, the number of edges in G is greater than the number of edges in H. So n1 > n1, which is not possible. Hence, G has no cycles and therefore is a tree.

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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