# Thread: number of subgraphs in a complete graph

1. ## number 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$

2. Originally Posted by sbankica
what is the number of subgraphs of the complete graph $\displaystyle K_n$ and the complete bipartite graph $\displaystyle 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 $\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.

3. Originally Posted by Plato
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.
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?