Results 1 to 3 of 3

Math Help - number of subgraphs in a complete graph

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    37

    number of subgraphs in a complete graph

    what is the number of subgraphs of the complete graph  K_n and the complete bipartite graph  K_r,_s
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,639
    Thanks
    1592
    Awards
    1
    Quote Originally Posted by sbankica View Post
    what is the number of subgraphs of the complete graph  K_n and the complete bipartite graph  K_r,_s
    While this is reasonable question, I have never seen it.
    I think that we must assume that these are labeled graphs.
    On n labeled vertices there are 2^{\frac{n(n+1)}{2}} possible graphs.
    Now each of those is a subgraph of K_n.
    However, that is not the answer to this question because each of those includes all of the vertices.
    AND that does not need to be the case. As of now, I do know how to expand that number.
    Any of these graphs that have vertices of degree zero can be multiple subgraphs.
    Thus, how do we count all of those possibilities?

    I hope this helps.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2010
    Posts
    18
    Quote Originally Posted by Plato View Post
    While this is reasonable question, I have never seen it.
    I think that we must assume that these are labeled graphs.
    On n labeled vertices there are 2^{\frac{n(n+1)}{2}} possible graphs.
    Now each of those is a subgraph of K_n.
    However, that is not the answer to this question because each of those includes all of the vertices.
    AND that does not need to be the case. As of now, I do know how to expand that number.
    Any of these graphs that have vertices of degree zero can be multiple subgraphs.
    Thus, how do we count all of those possibilities?

    I hope this helps.
    Plato, am I counting these properly?
    Assume that a vertex set implies they are connected by an edge

    K_1 has 1 subgraph (V{a})
    K_2 has 3 subgraphs (V{a}, V{b}, V{a,b} )
    K_3 has 7 subgraphs (V{a}, V{b}, V{c}, V{a,b}, V{b,c}, V{c,a}, V{a,b,c} )

    or is
    K_3 has 10 subgraphs (V{a}, V{b}, V{c}, V{a,b}, V{b,c}, V{c,a}, V{a,b,c} E{ab,bc}, V{a,b,c} E{ac,cb}, V{a,b,c} E{cb,ba}, V{a,b,c} E{ab,bc,ca})

    Where can we go from here?
    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, 09:59 AM
  2. complete the table, graph the functions.
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: October 19th 2010, 05:36 AM
  3. Minimum number to remove from a complete graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 14th 2010, 03:11 PM
  4. the complete graph k5
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 26th 2009, 04:52 PM
  5. Help complete a graph?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 20th 2008, 03:59 PM

Search Tags


/mathhelpforum @mathhelpforum