Consider an undirected graph with 25 vertices x2 x3 x26 wit

Consider an undirected graph with 25 vertices x_2, x_3, ..., x_26 with edges (x_i, x_j) if and only if integers i and j have a common divisor. How many components does this graph have? Find a spanning tree for each component.

Solution

it\'s easy to calculate the number of edges as 114.

There are a few vertices with no edges. Those have prime index p where 2p > 26, so that there are no vertices you can connect to. Those would have index 17 19 and 23
All even vertices are connected. There are 13 which I won\'t bother to list.

All multiples of 3 are connected, and since 6 is an even multiple of 3, it\'s connect to the even vertices.
All multiples of 5, 7, 11 and 13 are also connected to the even mulktiples, through vertices 10 14 22 and 26.

So you are looking at 17 23 19 as isolated vertices.

A spanning tree of the other 22 veritices could be:
Start at 2 and go to 4 6 8 10 12 14 16 18 20 22 24 26
Branch at 6 to go to 3 9 15 21, the odd multiples of 3
Branch at 10 to go to 5 25, the multiples of 5 not a multiple of 2 or 3
Branch at 14 to go to 7
Branch at 22 to go to 11
Branch at 16 to go to 13

There are many, many ways to get a spanning tree. Note that 7 11 and 13 can branch to only one point, so each of those must be the end of a leaf