# Number of cycles of length 3 on n vertices. Cycles of length 4?

How many cycles of length 3 are possible for a complete graph with n vertices? Cycles of length 4?

My first thought for both scenarios was $n \choose 3$ * $\frac{1}{2}$ ->(cycle lengths of 3) and $n \choose 4$ * $\frac{1}{2}$ -> (cycle lengths of 4). The 1/2 is there to take care of the direction of the cycle "left" or "right" and the combination takes care of choosing 3 or 4 vertices needed for the cycles to occur. Is this a correct line of logic?

• If you mean in a complete graph on $n$ vertices this seems right. – Arthur Apr 19 '16 at 6:20
• When $n=3$, your first formula gives you one-half. When $n=4$, your second formula gives one-half. So clearly something is wrong. Also, in the title, you have cycles of length 3, but in the body, you have paths. – Gerry Myerson Apr 19 '16 at 7:06
• Can you please state the question clearly in the body? – shardulc Apr 19 '16 at 7:30
• Why do you mention "loops" in the title? A loop is a cycle of length $1,$ right? – bof Apr 19 '16 at 10:33

We have $n$ vertices and want to find cycles of length $k \leq n$. We assume that a cycle $ABCA$ is distinct from a cycle $BCAB$ and also from $ACBA$ (i.e. starting point and direction matter). We choose $k$ vertices from $n$ in a particular order: there are $k! \cdot \binom{n}{k}$ ways to do this. Such a choice completely specifies a cycle, starting with the first vertex chosen and ending with an edge from the last vertex to the first vertex.
If a cycle $ABCA$ is distinct from $BCAB$ but not from $ACBA$, then we divide the $k! \cdot \binom{n}{k}$ cycles above by 2, because each cycle is counted twice (once in either direction). Thus the number of cycles is $\frac{k! \cdot \binom{n}{k}}{2}$. This formula does not apply for $k = 1$ or $k = 2$ because in both cases, direction does not make a difference.
If a cycle $ABCA$ is distinct from $ACBA$ but not from $BCAB$, then we divide the $k! \cdot \binom{n}{k}$ cycles above by $k$, because each cycle is counted $k$ times for each starting point. Thus the number of cycles is $\frac{k! \cdot \binom{n}{k}}{k} = (k-1)! \cdot \binom{n}{k}$. Again, this is not relevant for $k = 1$ or $k = 2$.
Think about what $n \choose 3$ really does: it chooses three vertices among the $n$ possible vertices. Since you don't choose them with order, you haven't chosen a "direction" of the cycle. As said in the comment $\frac12 {n\choose 3}$ gives $\frac12$ for $n=3$. However there is exactly one cycle of length 3 on 3 vertices. That's why the $\frac12$ shouldn't be there in the formula that counts the number of 3-cycles (picking 3 vertices gives you one and exactly one 3-cycle).
Counting the number of paths of length 4 has to be done differently. Your formula says "pick 4 vertices without order". However, if I give you 4 vertices without order, there is more than one way to build a path of length 4. How many exactly? Then, do you still need to divide by $2$ because you counted each path twice?