0
$\begingroup$

Are all maximal subtrees of a simple connected graph isomorphic? any hints?

1 Answers 1

3

The answer is a resounding "No". Even as small as the complete graph on four vertices, one can find nonisomorphic spanning trees.

enter image description here enter image description here

The number of nonisomorphic trees grows reasonably quickly after that. For example, the complete graph on ten vertices has 106 nonisomorphic spanning trees.

(Incidentally, here is a small collection of spanning trees you might find interesting.)

  • 0
    Thanks, a lot, for the link too, it seems interesting. I will have a look2012-10-11