Can someone check these (bit skeptical of my answers).

a) How many copies of $C_4$ in $K_n$?

Picking any 4 vertices can be used to give a copy of $ C_4 $of each of these there are $4!$ ways in which the vertices can be arranged but this overcounts by a factor of 8 (4 vertices $ \times $ 2 directions that can be transversed) so the total is $ (4!/8)* nC4=3(nC_4)$.

b) How many copies of $P_3$ in $K_n$?

Any 4 vertices choose represent $4C3 = 4 $paths so we have 4(nC4) in total.

How can the answer to a be smaller than the answer to b when we have that every$ P_3 $ in $K_n$ is contained within a $C_4$ in $K_n$?

No idea about this part any help?


  • $\begingroup$ Part a is good, For part b why do you want to use part a? You can solve part b using similar techniques. $\endgroup$
    – Asinomás
    Jan 7 '15 at 21:15

For the first question look here

For the second question there are $\binom{n}{3}$ ways to select the three vertices in the path. And after that there are $3$ ways to select which of the $3$ vertices is going to be the middle one, so $3\binom{n}{3}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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