Results 1 to 6 of 6

Math Help - n-vertex graph

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    n-vertex graph

    I'm having trouble applying it!
    Last edited by Showcase_22; November 26th 2009 at 12:29 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by Showcase_22 View Post
    Determine the number of n-vertex labelled graphs without isolated vertices (ie. without vertices of degree 0).
    For the sake of ease of notation, define E(n)=\frac{n(n-1)}{2}.
    That is maximum number of edges in a simple graph on n vertices.
    Hence there are 2^{E(n)} labeled simple graphs on n vertices.

    Now we must remove any of those graphs having null vertices.
    I(n) = \sum\limits_{k = 0}^n {\left( { - 1} \right)^k\binom{n}{k} \cdot 2^{E(n - k)} }
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    Just so i'm clear, is I(n) the number of vertices?

    Also, what about graphs that aren't simple? From the question, "without vertices of degree 0" as a definition for isolated vertices implies that we are dealing with simple graphs. However, it isn't explicitly stated!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by Showcase_22 View Post
    Just so i'm clear, is I(n) the number of vertices? Also, what about graphs that aren't simple? From the question, "without vertices of degree 0" as a definition for isolated vertices implies that we are dealing with simple graphs. However, it isn't explicitly stated!
    I(n) is the number graphs on n vertices with no isolated vertices( zero degree).

    A non-simple graph is one with more than one edge between two vertices or contains a loop or could be a directed graph.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    so we still need to add on the number of non-simple graphs.

    We could just have a graph where every point maps to itself, we have't included that yet.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1780
    Awards
    1
    Quote Originally Posted by Showcase_22 View Post
    so we still need to add on the number of non-simple graphs.
    We could just have a graph where every point maps to itself, we have't included that yet.
    I have no idea what you are talking about there.
    Do you understand of sort of graphs we are dealing with here?

    Insofar as I know the problem of counting labeled graphs only comes up for simple graph.
    Oddly enough it is easier to count labeled graphs then it is to count unlabeled graphs.

    There is no ‘mapping’ involved in a graph itself.
    So what sense does it make to say "where every point maps to itself"?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Central and Bicentral vertex in graph
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: January 29th 2011, 10:06 AM
  2. [SOLVED] graph vertex colouring
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 2nd 2010, 11:46 AM
  3. vertex basis for the graph
    Posted in the Geometry Forum
    Replies: 2
    Last Post: June 7th 2010, 04:58 AM
  4. Finding the vertex of the parabolic graph
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: October 28th 2008, 03:15 PM
  5. How to find vertex of a graph or equation
    Posted in the Calculus Forum
    Replies: 14
    Last Post: June 6th 2008, 08:57 PM

Search Tags


/mathhelpforum @mathhelpforum