Graph Theory - please help
I've read through all of my class notes and looked at a number of online tutorials. But questions like this still stump me. My main problem is I have absolutely no idea what it means.
G is a graph with 25 vertices $\displaystyle x_2, x_3, . . . , x_{26}$ and edges
$\displaystyle \{x_i, x_j\} \Leftrightarrow gcd(i, j) > 1$.
(a) Find the number of connected components.
(b) Find a spanning tree for each component.
If somebody could explain the gcd edges part to me in plain English that would be great. Also, does anybody know any good tutorials that have explanations and algorithms that would help me solve a and b? I'm sure this is simple enough, but I don't know where to start.