# How many connected components does this graph contain?

• Nov 26th 2009, 04:34 AM
HenrySellers
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

Not a clue of these, any help would be much appreciated, THANKS!!
• Nov 27th 2009, 01:09 PM
qmech
A start
For the 1st question, you have 25 points labelled
$
x_2,x_3,x_4,x_5,....x_{26}
$

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