what is the number of subgraphs of the complete graph and the complete bipartite graph

Printable View

- March 26th 2010, 02:12 PMsbankicanumber of subgraphs in a complete graph
what is the number of subgraphs of the complete graph and the complete bipartite graph

- March 26th 2010, 04:04 PMPlato
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 possible graphs.

Now each of those is a subgraph of .

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. - March 29th 2010, 12:04 PMCelcius
Plato, am I counting these properly?

Assume that a vertex set implies they are connected by an edge

has 1 subgraph (V{a})

has 3 subgraphs (V{a}, V{b}, V{a,b} )

has 7 subgraphs (V{a}, V{b}, V{c}, V{a,b}, V{b,c}, V{c,a}, V{a,b,c} )

or is

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?