Generating random solution in python - Tabu Search - Graph

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 have to generate a random tree. I have a .txt file with the information about the graph I already have, and from this graph I have to generate a random tree (doesn't matter the size of it)

I am reading and looking for libraries and would be nice if anyone could share some ideas, hints or useful links. Thank you!