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

Now you have to draw edges connecting the points. The rule you give is
and 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
and ? No, because gcd(2,3) = 1.
and ? Yes, because gcd(2,4) = 2.
...
and ? Yes, because gcd(12,15) = 3.
...
and you should be able to keep on going.