Solution 4.2.12.1.

  1. No, although there are graphs for which this is true. For example, \(K_4\) has a spanning tree that is a path (of three edges) and also a spanning tree that is a star (with center vertex of degree 3).

  2. Yes. For a fixed graph, we have a fixed number \(v\) of vertices. Any spanning tree of the graph will also have \(v\) vertices, and since it is a tree, must have \(v-1\) edges.

  3. No, although there are graph for which this is true (note that if all spanning trees are isomorphic, then all spanning trees will have the same number of leaves). Again, \(K_4\) is a counterexample. One spanning tree is a path, with only two leaves, another spanning tree is a star with 3 leaves.

in-context