# 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
\$\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.