How can I generate a random tree in python?

Question

I want to implement Tabu Search in Python to solve a problem related to a Graph (finding trees, coloring problem and that kind of stuff). I have written basic codes in Python and that's the first time I am writing something like that. I know how the algorithm works (in theory) and I am having some trouble to implement it.

What's the best way to generate the random solution so I can start the algorithm? I want to generate a random tree from an initial graph:

graph = { "a" : ["c"],
      "b" : ["c", "e"],
      "c" : ["a", "b", "d", "e"],
      "d" : ["c"],
      "e" : ["c", "b"],
      "f" : []
    }

I'm using these functions to see the edges and isolated nodes:

def generate_edges(graph):
    edges = []
    for node in graph:
        for neighbour in graph[node]:
            edges.append((node, neighbour))

    return edges

print(generate_edges(graph))


def find_isolated_nodes(graph):
    """ returns a list of isolated nodes. """
    isolated = []
    for node in graph:
        if not graph[node]:
            isolated += node
    return isolated

print(find_isolated_nodes(graph))

And this one to find the paths:

def find_all_paths(self, start_vertex, end_vertex, path=[]):
""" find all paths from start_vertex to
    end_vertex in graph """
graph = self.__graph_dict
path = path + [start_vertex]
if start_vertex == end_vertex:
    return [path]
if start_vertex not in graph:
    return []
paths = []
for vertex in graph[start_vertex]:
    if vertex not in path:
        extended_paths = self.find_all_paths(vertex,
                                             end_vertex,
                                             path)
        for p in extended_paths:
            paths.append(p)
return paths

What I need is to find a tree as a random solution so I can change it until is the biggest possible one in the graph I have.

What could be the best way to do that? Thank you.