How many connected components does this graph contain?

Q1. Let F

be the graph with 25 vertices x2, x3, . . . , x26 and edges

{

xi, xj} <----> gcd(i, j) > 1.

How many connected components does this graph contain?

And find a spanning tree for each component.

Q2.

A rooted tree of height

h is said to be balanced if its leaves are

all at level h or h − 1. For a given k, prove that the height of

an m-ary rooted tree with k leaves is minimised when the tree

is balanced.(Headbang)(Headbang)(Headbang)

Not a clue of these, any help would be much appreciated, THANKS!!