7
$\begingroup$

How many number of cycles are there in a complete graph?

Is there any relation to Symmetric group?

$\endgroup$
6
  • $\begingroup$ Cycles or induced cycles? $\endgroup$ Jul 17, 2015 at 0:19
  • $\begingroup$ It's an induced subgraph isomorphic to a cycle graph. $\endgroup$ Jul 17, 2015 at 0:35
  • $\begingroup$ en.wikipedia.org/wiki/Cycle_graph $\endgroup$ Jul 17, 2015 at 0:37
  • $\begingroup$ In a complete graph, a subgraph consisting of three points is an induced cycle, but any larger subgraph is not. $\endgroup$ Jul 17, 2015 at 0:38
  • $\begingroup$ I dont understand. I know that any 3 points of $K_n$ is a cycle. What is an induced cycle here? $\endgroup$
    – Turbo
    Jul 17, 2015 at 0:42

3 Answers 3

15
$\begingroup$

We can use some group theory to count the number of cycles of the graph $K_k$ with $n$ vertices. First note that the symmetric group $S_k$ acts on the complete graph by permuting its vertices. It's clear that you can send any $n$-cycle to any other $n$-cycle via this action, so we say that $S_k$ acts transitively on the $n$-cycles. The orbit-stabilizer theorem states that the order of a group acting transitively on a set, is the product of the size of the set and the size of the subgroup stabilizing an element of the set. In this case, we can stabilize an $n$-cycle by permuting the $k-n$ vertices not involved in the cycle, and then permuting the $n$ vertices in the cycle in a way that preserves the cycle. This gives us that the cycle stabilizer has size $(k-n)!\cdot 2n.$ Now we have $$|S_k| = (\text{number of n-cycles})((k-n)!\cdot 2n). $$ hence the number of $n$-cycles is $\frac{k!}{(k-n)!\cdot 2n}$. The total number of cycles can be computed as a sum: $$\sum_{i=3}^k \frac{k!}{(k-i)!\cdot 2i}.$$ I'm not sure whether this sum simplifies.

Here the group theory doesn't add much to the counting, over the usual overcounting-and-dividing solution to this type of problem. However it demonstrates that this technique is a special case of a more general result, and gives a concrete example with which to understand it.

$\endgroup$
4
  • $\begingroup$ Are you looking at only simple cycles? $\endgroup$
    – Turbo
    Jul 17, 2015 at 10:45
  • $\begingroup$ Yes this is only considering simple cycles. Non simple cycles can also be counted, but require a different technique - one approach employs some linear algebra. I'd be glad to elaborate. $\endgroup$ Jul 21, 2015 at 16:38
  • $\begingroup$ This is the number of undirected simple cycles. The term "cycle" can also be used for directed simple cycles (in an undirected graph), of which there are twice as many. (See the distinction made at en.wikipedia.org/wiki/Cycle_%28graph_theory%29.) This corresponds to two OEIS sequences, A002807 for undirected cycles and A119913 for directed cycles. If you omit the $2$ (i.e. count directed cycles) and include the terms for $i=1,2$ in the sum, you get A002104, the logarithmic numbers. $\endgroup$
    – joriki
    Jul 23, 2015 at 7:19
  • $\begingroup$ I think answer is wrong. Number of $k$ cycles is $\binom{n}{k-1}(k-1)!+\binom{n-1}{k-1}(k-1)!+\dots+\binom{k-1}{k-1}(k-1)! =\Big(\binom{n}{k-1}+\binom{n-1}{k-1}+\dots+\binom{k-1}{k-1}\Big)(k-1)!$. $\endgroup$
    – Turbo
    Jul 26, 2015 at 1:06
11
$\begingroup$

From $K_n$ lets pick a number $p$, $p \le n$ where $C_p$ is a cycle of length $p$.

Let $2\to 3\to 4\to 5\to 1\to\dots\to (p-1)\to 2$ be any arbitrary $C_p$. (note that the first and last vertex are same).

Now we fix the first vertex(which is also the last vertex since it is a cycle) like: $$ 2\to [3\to 4\to 5\to 1\to\dots\to (p-1)]\to 2 $$ We have $(p-1)!/2$ different cycles if we permute the section within the square brackets '$[]$' (circular permutation).

Now, from $K_n$ we can choose $p$ vertex in $\dbinom np$ ways and each of the $p$ vertex has $(p-1)!/2$ cycles.

Therefore the total number of cycles in $K_n$ is $$ \sum_{p=3}^{n} \binom np \frac{(p-1)!}{2}. $$

$\endgroup$
0
$\begingroup$

In a complete graph, every choice of n vertices is a cycle, so if the graph has k vertices, then there is $\sum_{n=3}^{k} {k \choose n}$, which is equal to $ \dfrac{-k^2}{2}-\dfrac{k}{2}+2^k-1$. As for the symmetric group, I'm pretty sure that it is the automorphism group for the complete graph of the same size.

$\endgroup$
1
  • $\begingroup$ Order is somewhat important. A subset of 4 vertices forms 3 cycles of length 4. $\endgroup$
    – user58697
    Jul 17, 2015 at 0:49

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.