Results 1 to 5 of 5

Math Help - Graph Theory

  1. #1
    Newbie
    Joined
    Mar 2009
    Posts
    3

    Graph Theory

    I have been trying to find out the maximum number of edges in a indirect graph with N vertices and how to prove it without any luck, any help would be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,649
    Thanks
    1597
    Awards
    1
    Quote Originally Posted by skiing64 View Post
    I have been trying to find out the maximum number of edges in a indirect graph with N vertices and how to prove it without any luck, any help would be greatly appreciated.
    Not sure what is meant by indirect graph.
    Do you mean a simple nondirected graph?
    If so the answer is quite simple: {N \choose 2}=\frac {N(N-1)}{2}.

    If not, please define the terms used in this question.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2009
    Posts
    3
    not directed is not having arrows pointing in a direction but how do you prove that is correct?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,649
    Thanks
    1597
    Awards
    1
    In a simple graph, any two vertices determine at most one edge.
    Therefore, the maximum number of edges on N vertices equals N choosing 2.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2009
    Posts
    3
    Thanks I was going about that the right way then
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 05:47 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 09:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum