Results 1 to 5 of 5

Math Help - Number of Graphs

  1. #1
    Junior Member
    Joined
    Aug 2010
    Posts
    57

    Number of Graphs

    I came across a formula for number of graphs on n vertices as  2^(^n^c^2^)

    Can anyone explain me how this formula is arrived.

    I trying to find by having adjacency matrix representation of a graph in mind. But i am not able to achieve this.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,910
    Thanks
    1759
    Awards
    1
    Quote Originally Posted by kumaran5555 View Post
    I came across a formula for number of graphs on n vertices as  2^(^n^c^2^)
    Your notation is almost too poor to read.

    Do you mean 2^{\binom{n}{2}}=2^{\frac{n(n-1)}{2}}~?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    There are nC2 pairs of vertices. Each of them can be or not be an edge.

    An adjacency matrix for a simple undirected graph (at most one edge between two vertices and no loops) is symmetric and has 0's on the diagonal. The number of elements in the half above the diagonal is n(n - 1)/2 = nC2. Each of them can be 0 or 1.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,910
    Thanks
    1759
    Awards
    1
    If my guess is correct, that number on the OP is for simple graphs on n labels. The more general question about unlabeled simple graph is much more difficult.
    There are only four unlabeled simple graph of order three.
    However that are, 2^{\binom{3}{2}}=8 labeled simple graphs of order three.

    We choose the labels two at a time to form the edges.
    Any subset of edges is a graph.

    Polya solved the unlabeled simple graph problem in 1935. But very complicated.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Aug 2010
    Posts
    57
    Thanks.

    I think it almost similar to the way we prove for number of reflexive relations of a set with n elements.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: April 28th 2011, 07:20 AM
  2. interval graphs and chromatic number
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 22nd 2010, 02:52 PM
  3. Find the number of graphs such that...
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 8th 2009, 01:51 AM
  4. Number of directed graphs with no cycles
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 23rd 2009, 06:18 AM
  5. Replies: 2
    Last Post: December 18th 2008, 06:28 PM

Search Tags


/mathhelpforum @mathhelpforum