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!!

For the 1st question, you have 25 points labelled
$\displaystyle
x_2,x_3,x_4,x_5,....x_{26}
$
Now you have to draw edges connecting the points. The rule you give is
$\displaystyle x_n$ and $\displaystyle x_m$ are connected iff gcd(n,m) > 1.
Recall that gcd(n,m) = greatest common divisor of n and m. (Think - what's the biggest integer that goes into both n and m?)

So let's try drawing edges. Do we draw an edge between
$\displaystyle x_2$ and $\displaystyle x_3$? No, because gcd(2,3) = 1.
$\displaystyle x_2$ and $\displaystyle x_4$? Yes, because gcd(2,4) = 2.
...
$\displaystyle x_{12}$ and $\displaystyle x_{15}$? Yes, because gcd(12,15) = 3.
...
and you should be able to keep on going.