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 Threads - graph theory HELP Date
I Representing Tiling and Packing Solutions May 26, 2017
What does it mean? (Graph theory) Feb 26, 2016
Graph Theory Help! Aug 2, 2011
Need help – Graph Theory Oct 13, 2010
Help with graph theory Sep 23, 2010