Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
Note your formula assumes $n\geq 3$. For $n=1$ and $n=2$, it would not work... –  Arturo Magidin Apr 24 '12 at 3:29

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

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.