Results 1 to 5 of 5

Math Help - Maximum size of G

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Maximum size of G

    Let G be a graph of order n that is not connected. What is the maximum size of G?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,913
    Thanks
    1760
    Awards
    1

    Re: Maximum size of G

    Quote Originally Posted by alexmahone View Post
    Let G be a graph of order n that is not connected. What is the maximum size of G?
    What is meant by "the size of G"?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Maximum size of G

    Quote Originally Posted by Plato View Post
    What is meant by "the size of G"?
    the number of edges in G
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,913
    Thanks
    1760
    Awards
    1

    Re: Maximum size of G

    Quote Originally Posted by alexmahone View Post
    the number of edges in G
    Here is a classic problem.
    If \|\mathcal{E}\| is the number of edges and \|\mathcal{E}\|>\frac{(n-1)(n-2)}{2} prove the graph is connected.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Maximum size of G

    Quote Originally Posted by Plato View Post
    Here is a classic problem.
    If \|\mathcal{E}\| is the number of edges and \|\mathcal{E}\|>\frac{(n-1)(n-2)}{2} prove the graph is connected.
    The maximum number of edges in a graph of order n-1 is \binom{n-1}{2}=\frac{(n-1)(n-2)}{2}. If we add another vertex, any new edge will have to join the new vertex to one of the original n-1 vertices and the graph becomes connected.

    So, are you saying that the answer to my question in post #1 is \binom{n-1}{2}?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. maximum matching and size
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 5th 2011, 03:04 PM
  2. Replies: 1
    Last Post: July 12th 2010, 05:58 AM
  3. Replies: 3
    Last Post: December 14th 2009, 12:20 PM
  4. Maximum size of error
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: December 2nd 2009, 05:25 PM
  5. Size!
    Posted in the Math Challenge Problems Forum
    Replies: 4
    Last Post: November 16th 2009, 04:40 PM

Search Tags


/mathhelpforum @mathhelpforum