what is the number of subgraphs of the complete graph $\displaystyle K_n$ and the complete bipartite graph $\displaystyle K_r,_s$

Printable View

- Mar 26th 2010, 01:12 PMsbankicanumber of subgraphs in a complete graph
what is the number of subgraphs of the complete graph $\displaystyle K_n$ and the complete bipartite graph $\displaystyle K_r,_s$

- Mar 26th 2010, 03: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 $\displaystyle 2^{\frac{n(n+1)}{2}}$ possible graphs.

Now each of those is a subgraph of $\displaystyle 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. - Mar 29th 2010, 11:04 AMCelcius
Plato, am I counting these properly?

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

$\displaystyle K_1$ has 1 subgraph (V{a})

$\displaystyle K_2$ has 3 subgraphs (V{a}, V{b}, V{a,b} )

$\displaystyle 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

$\displaystyle 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?