Results 1 to 3 of 3

Math Help - QUESTION about complete graph

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    7

    QUESTION about complete graph

    1. Fix n 3 to be an integer. How many graphs are there that aresub-graphs of Kn (assume that all nodes are different and included in the sub-graph)?

      Thanks Brothers !
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,969
    Thanks
    1788
    Awards
    1

    Re: QUESTION about complete graph

    Quote Originally Posted by kakatomy View Post
    Fix n ≥ 3 to be an integer. How many graphs are there that are sub-graphs of Kn (assume that all nodes are different and included in the sub-graph)?
    I not sure that I understand that statement.

    There are 2^n-1 non-empty subsets of vertices.

    If we chose a subset of vertices and include any edge between any two of them, then that is the number of sub-graphs.

    Now some authors do not allow single vertex sub-graphs.
    In that case we use the number 2^n-n-1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2011
    Posts
    24

    Re: QUESTION about complete graph

    Hi, if that is the wording of your problem, with the "fix n \geq 3," then I think something is missing, because the solution does not depend on n \geq 3 at all. Do you mean connected subgraphs? Do you include the order-zero graph?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Wheel graph and complete graph
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 29th 2012, 06:56 PM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 15th 2011, 10:59 AM
  3. complete the table, graph the functions.
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: October 19th 2010, 06:36 AM
  4. the complete graph k5
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 26th 2009, 05:52 PM
  5. Help complete a graph?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 20th 2008, 04:59 PM

Search Tags


/mathhelpforum @mathhelpforum