0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If you mean in a complete graph on $n$ vertices this seems right. $\endgroup$ – Arthur Apr 19 '16 at 6:20
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Apr 19 '16 at 7:06
  • $\begingroup$ Can you please state the question clearly in the body? $\endgroup$ – shardulc Apr 19 '16 at 7:30
  • $\begingroup$ Why do you mention "loops" in the title? A loop is a cycle of length $1,$ right? $\endgroup$ – bof Apr 19 '16 at 10:33
1
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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?

$\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.