Exercise 12.

Unless it is already a tree, a given graph \(G\) will have multiple spanning trees. How similar or different must these be?

1. Must all spanning trees of a given graph be isomorphic to each other? Explain why or give a counterexample.

2. Must all spanning trees of a given graph have the same number of edges? Explain why or give a counterexample.

3. Must all spanning trees of a graph have the same number of leaves (vertices of degree 1)? Explain why or give a counterexample.