Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The graph theory HELP

  1. Apr 8, 2009 #1
    The graph theory HELP!!!

    How many distinct graphs can be found by the set V={1,2,....,n} with k edges?

    For this question i conclude that totao.l number of distinct graphs comes with 2^(choose two in n)

    but i cannot find the solution which gives the relation with k edges can you help me?
  2. jcsd
  3. Apr 8, 2009 #2
    Re: The graph theory HELP!!!

    There are a total of (n^2 - n)/2 = 1/2 n(n-1) pairs of vertices. You pick k out of these, so you have Comb(1/2 n(n-1), k) possibilities.

    If you're talking about directed graphs, multiply this by 2. If you allow for loops, take 1/2 n^2 instead of 1/2 n(n-1).
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: The graph theory HELP
  1. Graph Theory (Replies: 1)

  2. Help with graph theory (Replies: 11)

  3. Graph Theory Help! (Replies: 0)