I want to count the number of simple graphs on $n$ vertices where it is given that there is a fixed $K_k$ among those $n$ vertices. The way I am reasoning is this: the edges within the $n-k$ non-$K_k$ vertices can be filled out in $2^{\tbinom{n-k}{2}}$ ways, and for each of the $k$ vertices $v_1,\cdots v_k$, the edges from $v_i$ to the $n-k$ non-$K_k$ vertices can be filled out in $2^{n-k}$ ways. This yields a total of $2^{k(n-k)}2^{\tbinom{n-k}{2}}$. Is this correct? Thanks.
Counting the number of graphs on n vertices
1
$\begingroup$
combinatorics
graph-theory
1 Answers
2
This is correct, but it seems a bit more complicated than necessary. You have a mixed term $kn$ in the exponent that cancels when you spell out the binomial coefficient. To avoid introducing it in the first place, you could argue that there are $\binom n2$ edges in all and $\binom k2$ of them are already determined, so the exponent is $\binom n2-\binom k2$.
By the way, in a case like this I'd specify that you want to count the number of labeled graphs.