Concerning a tutorial, I don't know much, but a long time ago this book: "Discrete Mathematics and Its Applications" by Kenneth Rosen was used in the Discrete Mathematics course in our university (it has new editions). It has chapters on graphs and trees. A more difficult higher-level standard reference for similar things is (or was) "Data Structures and Algorithms" by Aho, Ullman. I am sure there are many online sources as well, starting from Wikipedia.
For this problem, though, there may be some characteristic about this particular graph that follows from properties of GCD that makes it easier to find those things, and the general algorithm for finding spanning trees may not be the best thing. I am saying this without looking carefully into the problem, but I would advise trying to understand what kind of graph this is and what the definitions of these concepts are, and going into general algorithms later if needed.