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).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook