Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.