4
$\begingroup$

I've been given the following problem as homework:

Q: Compute the number of subgraphs of $K_{15}$ isomorphic to $C_{15}$.

$K_{15}$ means complete graph with 15 vertices. $C_{15}$ means cyclic graph, where the whole graph is a cycle, with 15 vertices. For example, $C_3$ is a triangle, $C_4$ is a square, and $C_5$ is a pentagon.

My efforts: In order to try to figure out a general formula for $C_n$, I tried doing this problem with $C_5$. After a huge amount of trial and error, it looks like the formula is something like $$\binom{15}{n}\binom{n-1}{2}(n-3)!$$
However, I can't seem to come up with a good reason for this formula or verify whether it's correct. I'm doubting it is correct.

This is homework, so I'm NOT looking for solutions. Could you give some tips for figuring this out?

$\endgroup$
  • 1
    $\begingroup$ Note your formula assumes $n\geq 3$. For $n=1$ and $n=2$, it would not work... $\endgroup$ – Arturo Magidin Apr 24 '12 at 3:29
1
$\begingroup$

The binomial coefficient $\binom{15}{n}$ selects the $n$ vertices that will be in the cycle.

I think you would be less confused if you rewrote the other factor: assuming $n\geq 3$, $$\binom{n-1}{2}(n-3)! = \frac{(n-1)(n-2)}{2}(n-3)! = \frac{(n-1)!}{2}.$$ It's even more suggestive if we write it as $$\frac{n!}{2\times n}.$$

Think of it as follows: $\binom{15}{n}$ selects the vertices. Now you need to select an order for those vertices so that you get a cycle (this will select the edges). How many ways can you order $n$ vertices? And when will two orderings give you the same cycle? The factor of $n$ and the factor of $2$ represent two different kinds of overcounting.

$\endgroup$
0
$\begingroup$

Let's start with the case $n = 3$. A triangle in $K_{15}$ is given by any three vertices. So the number of triangles is $\binom{15}{3}$.

Let's proceed to the case $n = 4$. A rectangle in $K_{15}$ is given by any four vertices. But the vertices $a,b,c,d$ define three different rectangles. Indeed, suppose that $a$ is connected to $b,c$, and let $d$ be the remaining vertex. Then the rectangle must be $$ab,bd,dc,ca$$ So the number of different rectangles is $\binom{15}{4} \cdot 3$.

When $n = 15$, there is only one way of choosing $15$ vertices. The earlier examples don't seem to help. Instead, I suggest trying to count how many copies of $C_n$ there are in $K_n$ for small $n$, and then generalize.

$\endgroup$

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.