AI Tutor
Back to Trees

Exercise 12

Avg difficulty 2.5

Unless it is already a tree, a given graph GG 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.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), §5.2 Trees, Exercise 12

AI Tutor

Adapted from Discrete Mathematics: An Open Introduction © 2013–2019 Oscar Levin. Licensed under CC BY-SA 4.0. Source: Discrete Mathematics: An Open Introduction. Imported at revision 1e2e26b.