Question 2.91

61. A connected graph H has a spanning tree with 26 edges. How many vertices does the spanning tree have? How many vertices does H have? What can one say about the number of edges H has?

61.

H’s spanning tree has 24 vertices; H has 24 vertices. H has at least 23 edges and, if there are no multiple edges, at most (24)(23)/2 edges.