Results 1 to 2 of 2

Math Help - How many connected components does this graph contain?

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    8

    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.

    Not a clue of these, any help would be much appreciated, THANKS!!
    Last edited by mr fantastic; November 27th 2009 at 05:20 PM. Reason: Changed post title
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2

    A start

    For the 1st question, you have 25 points labelled
    <br />
x_2,x_3,x_4,x_5,....x_{26}<br />
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Every connected graph contains a maximal tree
    Posted in the Differential Geometry Forum
    Replies: 4
    Last Post: October 4th 2011, 07:44 AM
  2. Edge connected graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 4th 2010, 11:08 AM
  3. k-connected graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 30th 2010, 05:26 PM
  4. Path connected components.
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: March 22nd 2009, 05:46 AM
  5. Connected components.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 18th 2007, 07:50 PM

Search Tags


/mathhelpforum @mathhelpforum