Generating all unlabeled trees with up to n nodes
1. Review


In Python, a docstring goes after the function or class introduction. So instead of:

""" return copy of graph with newNode node appended to toNode node """
def leaf_copy(graph, newNode, toNode):


write something like:

def leaf_copy(graph, newNode, toNode):
    """Return a copy of graph with newNode appended to toNode."""


There are several advantages of doing it this way. Docstrings are available via the help function in the interactive interpreter:

&gt;&gt;&gt; help(leaf_copy)
Help on function leaf_copy in module __main__:

leaf_copy(graph, newNode, toNode)
    Return a copy of graph with newNode appended to toNode.


Also, some integrated development environments (for example, PyCharm) can read and interpret docstrings to provide context-sensitive help or to generate reference documentation. And the built-in doctest module can automatically run examples in docstrings.
The trivial graph with one node and no edges is generated like this:

g = nx.Graph()
g.add_node(1)


but networkx has the function trivial_graph which does something similar.
The specification of genNextTreeList is:

""" get all n+1 node cases out of all n node cases in prevTreeList """


but this only the case if prevTreeList is the result of iterating genNextTreeList starting with an empty list. A more accurate specification would be something like this:

def genNextTreeList(prevTreeList):
    """Return a list of the graphs that can be constructed by attaching a
    new node to any of the nodes in any of the graphs in prevTreeList,
    except that if prevTreeList is None or the empty list, in which
    case a list containing the trivial graph is returned.

    """

It says in the Zen of Python,


  Special cases aren't special enough to break the rules.


so I would drop the special case. It is easy enough for the caller to pass the list containing the trivial graph, if that's what's wanted.

Also, it should be clear now that genNextTreeList does not only operate on trees. So a better name and specification would be something like this:

def augmented_graphs(graphs):
    """Return a list of the graphs that can be constructed by attaching a
    new node to any of the nodes in any of the graphs in the argument.

    """

Instead of having a flag isomorphic to determine whether the new graph has been found to be a duplicate, use Python's for ... else: ... statement, or the any or all functions.
There's no need to use networkx.algorithms.isomorphism.GraphMatcher: you could just call networkx.algorithms.isomorphism.is_isomorphic directly.
genNextTreeList has a two-step construction of the result: first, construct a list nextTreeList of augmented graphs, and second, eliminate duplicates. These could be combined into a single step by testing each new graph for isomorphism as soon as you construct it, like this:

from networkx.algorithms.isomorphism import is_isomorphic

def augmented_graphs(graphs):
    """Return a list of the graphs that can be constructed by attaching a
    new node to any of the nodes in any of the graphs in the argument.

    """
    result = []
    for old_graph in graphs:
        new_node = max(old_graph.nodes()) + 1
        for node in old_graph.nodes():
            new_graph = leaf_copy(old_graph, new_node, node)
            if not any(is_isomorphic(new_graph, g) for g in result):
                result.append(new_graph)
    return result

The top-level code does two things: it generates the free trees with up to N nodes, and it plots them. This would be better split into two functions each of which does a single thing, for example:

from networkx.generators.classic import trivial_graph

def free_trees(n):
    """Return list of free trees with up to n vertices."""
    result = trees = [trivial_graph()]
    for i in range(n - 1):
        trees = augmented_graphs(trees)
        result.extend(trees)
    return result



2. Alternative approach

A look at the NetworkX manual finds networkx.generators.nonisomorphic_trees.nonisomorphic_trees which implements the algorithm of


Robert Alan Wrights, Bruce Richmond, Andrew Odlyzko and Brendan D. Mckay (1986). “Constant time generation of free trees”. SIAM J. Comput. 15:2, pp. 540–548.


This generates the 19,320 free trees on 16 nodes (see A000055) in just over a second:

&gt;&gt;&gt; from networkx.generators.nonisomorphic_trees import nonisomorphic_trees
&gt;&gt;&gt; from timeit import timeit
&gt;&gt;&gt; timeit(lambda:list(nonisomorphic_trees(16)), number=1)
1.0307372510433197


Here are 100 of these trees: