Answer the following No explanation needed No partial credit

Answer the following. No explanation needed. No partial credit. Every edge of a tree is or is not a cut-edge? How many cycles, if any, can a tree have? A tree with n vertices has how many edges? Deleting a leaf from a tree with n vertices produces a tree with how many vertices? What is the parity of the number of vertices of a full binary tree (a rooted full 2-ary tree)? Parity is even or odd. How many leaves does a 3-ary tree have if it has 15 parents & every parent has exactly 3children? How many total internal vertices does a full 5-ary tree with n vertices have? How many different spanning trees does a complete bipartite graph K_2,2 have?/C_2,2 = C_4 (cycle with 4 vertices). How does one calculate the distance between 2 spanning trees?

Solution

(a) yes, every edge of a tree is a cut-edge.

(b) a tree can not have any cycle.

(c) a tree with n vertices has n-1 edges.

(d) deleting a leaf from a tree with n vertices produces a tree with n-1 vertices.

(e) a full binary tree has an odd number of vertices.

(f) There are 15 · 3 + 1 = 46 vertices since every vertex except the root is the child

of one of these 15 parents. Thus the number of leaves is 46 15 = 31