Results 1 to 4 of 4

Math Help - graph

  1. #1
    baz
    baz is offline
    Junior Member
    Joined
    Apr 2010
    Posts
    34

    graph

    Let v = { 1,2,3,4,5} be the set of vertices.How amny different graphs can be made with 'V' as set of vertices?

    Solution provided says that we can make 2^10 graphs ( without self loops).

    Does that make sense?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,962
    Thanks
    1784
    Awards
    1
    Quote Originally Posted by baz View Post
    Let v = { 1,2,3,4,5} be the set of vertices.How amny different graphs can be made with 'V' as set of vertices?
    Solution provided says that we can make 2^10 graphs ( without self loops).
    Does that make sense?
    Well it depends on what is meant by a graph.
    \binom{5}{2}=10 so on five vertices there are ten simple edges possible.
    In a directed graph each edge can have one of two directions (no two-way edges in a simple directed graph).
    In that case the answer is infact 2^{10}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    baz
    baz is offline
    Junior Member
    Joined
    Apr 2010
    Posts
    34
    But among 2^10 subsets, there is also a null set .Then how is graph possible with no edge.
    then it will be disconnected graph.
    Last edited by baz; April 29th 2010 at 08:09 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,962
    Thanks
    1784
    Awards
    1
    I was trying to make sense of the provided answer.
    It seems they are assumming a complete simple graph on five vertices.
    Then giving a direction to each edge.
    Otherwise, that answer does not work.
    Because there are 2^{10} simple non-directed graphs on five vertices.
    So there would be more directed graphs.
    I did say it depends on the definitions used.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 10:59 AM
  2. Replies: 7
    Last Post: August 5th 2011, 02:30 PM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 1st 2011, 04:30 AM
  4. Replies: 0
    Last Post: September 25th 2010, 06:59 AM
  5. Replies: 1
    Last Post: February 15th 2009, 06:35 AM

Search Tags


/mathhelpforum @mathhelpforum