Section 3.3 Trees
A tree is a connected graph with no cycles. Sage has commands which create all of the graphs of certain types, with trees being one of these types. We build the \(11\) non-isomorphic free (un-labeled) trees on \(7\) vertices. As in other areas of combinatorics, the command makes a generator that we can iterate over, though it lacks certain features like the .list() and .cardinality() methods. We use more basic Python commands instead.
Be careful, the generator named treegen will “remember” how much of it has been iterated over, and right now, it is exhausted, as we see.
So the call to the .next() method returns a StopIteration exception, which Python lets you catch with a try/except block. If we try to list the exhausted generator, we just get an empty list. The moral of the story is to rebuild the generator before employing it again. Remember, this may not be an expensive operation (i.e. take a long time) since the generator just re-initializes and will not build trees until you ask for them.
We rebuild the generator and now give a visual description of the \(11\) trees.
Notice how the output moves (generally) from low-degree vertices and large diameter to high-degree vertices and small diameter. This is due to an especially clever algorithm that builds each tree from its predecessor in a number of operations that is independent of \(n\text{.}\) So the only reason it takes longer to compute the number of trees on a larger number of vertices is because there are simply more of them. This algorithm is described in Constant Time Generation of Free Trees (R.A. Wright, B. Richmond, A. Odlyzko, B.D. McKay, - SIAM Journal on Computing, (1986)). Note that the generation of exhaustive lists of non-isomorphic objects is generally a hard problem, but for trees it turns out to be straightforward.
How many trees are there on \(17\) vertices? We thought you might never ask. We could build a list of all of them and see how long the list is. This might be an unsustainable strategy. Better–we will build each tree, count it, and throw it away. Our computation agrees with the entry of sequence A000055 of The On-Line Encyclopedia of Integer Sequences.
Cayley proved that there are \(n^{n-2}\) labeled trees on \(n\) vertices. We are going to verify this result for \(n = 9\) the hard way. We generate the \(47\) non-isomorphic graphs on \(n = 9\) vertices, and for each one we compute the full group of symmetries (the automorphism group, whose order allows us to count the number of fundamentally different ways to label the tree.
Which agrees with Cayley's \(9^7 = 4\,782\,969\text{.}\) Nice. Notice how a few substitutions would allow us to write this computation (fairly clearly) on a single line.
To see how to generate other different exhaustive collections of non-isomorphic graphs see the documentation for the graphs.nauty_geng() method, which is an interface to McKay's geng routine in his lightning-fast nauty package.