Are all maximal subtrees of a simple connected graph isomorphic? any hints?
Maximal subtrees of connected graph
0
$\begingroup$
graph-theory
1 Answers
3
The answer is a resounding "No". Even as small as the complete graph on four vertices, one can find nonisomorphic spanning trees.
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.)
-
0Thanks, a lot, for the link too, it seems interesting. I will have a look – 2012-10-11