how many 4-cycle are there in complete bipartite graph, for $k_{3,3}$ i know the answer is $9$ by choosing $\frac{6\times3\times2\times2}{2\times4}=9$ , where divide by 2 because it is oriented , and divide 4 because of 4 different starting point.

but is this question same as finding different hamiltonian circuit in complete bipartite graph? such as $\frac{n!(n-1)!}{2}= \frac{3!\times2!}{2} = 6$ its different but am i missing something important?

if graph is not bipartite, for example simple graph like Kn, ${}_6C_4\cdot \frac{(n-1)!}{2}$ , do i have to divide with different starting point like in bipartite graph?

  • $\begingroup$ In which complete bipartite graph? On $n$ vertices in general? $9$ isn't a function of $n$ (which changes according to the value of $n$)... $\endgroup$ – JMoravitz Nov 20 '19 at 19:48
  • $\begingroup$ @JMoravitz i'm sorry it is for k3,3 , but in general for kn,n is it the same with finding different hamilton circuit in complete bipartite graph? $\endgroup$ – fiksx Nov 20 '19 at 19:50
  • 1
    $\begingroup$ Now., a $4$-cycle in a complete bipartite graph will necessarily have two vertices from the first part, and two from the second part. Given such a selection, there is only one cycle that can be made with those four vertices. This leads to an answer of $\binom{n}{2}\binom{m}{2}$ for general $K_{n,m}$ and $9$ for the specific case of $K_{3,3}$. Note that a 4-cycle is not the same thing as a hamiltonian circuit. $\endgroup$ – JMoravitz Nov 20 '19 at 19:52
  • $\begingroup$ @JMoravitz ok but in simple graph for 3-cycle finding number of cycle in graph is same as finding number of hamilton cycle (?) $\endgroup$ – fiksx Nov 20 '19 at 20:08
  • $\begingroup$ What? Why should those at all be related? While yes, the number of hamiltonian cycles is equivalent to the number of cycles of length $n$ in a graph on $n$ vertices (because after all, a cycle of length $n$ is by definition what a hamiltonian cycle is in the first place for a graph with $n$ vertices), this number is not necessarily going to be the same as the number of cycles of length $k$ in a graph on $n$ vertices with $n$ different than $k$. $\endgroup$ – JMoravitz Nov 20 '19 at 20:08

Collating comments above and trying to answer any remaining loose ends...

Rather than blindly trying to apply formulas, you need to stop and think about where the formulas come from and how to derive them. Find the logic in what the formula means and where it comes from. In doing so, you will then be able to more accurately determine if a formula is correct and be able to come up with new formulas for scenarios you had yet to discuss.

The number of $k$-cycles in $K_n$ is $\binom{n}{k}\frac{(k-1)!}{2}$

To see this, we first select which $k$ of the $n$ vertices are used in the cycle. This selection of which vertices are used can be accomplished in $\binom{n}{k}$ ways.

Now, given a particular selection of vertices, we need still to determine in what order they appear in the cycle, noting that several cycles are indistinguishable. In order to help facilitate a count, we can assume that the vertices were labeled with some sort of specific order in mind (e.g. if the vertices represented people, they could be arranged according to age, or arranged according to height). Without loss of generality, suppose the vertices of the graph were labeled as the numbers $1,2,3,\dots,n$. Given such an ordering, among our selected vertices, one of them is going to be the "smallest" vertex. We will use that vertex as our reference point.

Now, we have our $k$ vertices, one of which is being used as a reference point. Let us arrange the remaining selected vertices around cycle. Choose which vertex appears "after" the smallest. Then choose which vertex appears after that, and then choose which appears after that, etc... until all vertices have been placed. This can be done in $(k-1)\cdot (k-2)\cdots 3\cdot 2\cdot 1 = (k-1)!$. Recognize however that this overcounts as the cycle where we had placed these same vertices in the reverse order is the "same cycle." The cycle (1 2 3 4 5 6) is the same as the cycle (1 6 5 4 3 2) in this context. To correct the count, we divide by two since this is the number of times we had counted every possibility when we intended to have only counted each possibility exactly once.

This gives our final result of the number of $k$-cycles in $K_n$ as being $\binom{n}{k}\frac{(k-1)!}{2}$

The number of hamiltonian cycles in $K_n$ is $\frac{(n-1)!}{2}$

To see this, just apply the earlier result using $k=n$ and recognize that every $n$-cycle in $K_n$ is a hamiltonian cycle and vice versa so the counts should be the same. Note that a hamiltonian cycle uses all $n$ of the vertices, not just four of them...

The number of $2k$ cycles in $K_{n,m}$ is $\binom{n}{k}\binom{m}{k}\frac{(k-1)!k!}{2}$

To see this, begin by noting that any $2k$ cycle in $K_{n,m}$ must have exactly $k$ elements from the first part and $k$ elements from the second part due to the nature of how bipartite graphs work. It is worth pointing out here as well that bipartite graphs have no odd-length cycles. So, we continue by selecting which $k$ elements were used from the first part and which $k$ elements were used from the second part in $\binom{n}{k}\binom{m}{k}$ ways.

Note that we are not done yet. Now that we have the elements, we still need to decide in what order they appear in the cycles. In the special case of $k=2$, so us looking at $4$-cycles we can quickly see that there is only one arrangement of these into a cycle possible. That is obviously not the case for larger $k$. There can be many many ways to arrange the elements into cycles, so let us count those ways.

We continue as before by noting that we could have applied some arbitrary order to the vertices ahead of time. Without loss of generality, we suppose again that the vertices were labeled $1,2,3,\dots,m+n$. Let us use as our reference point when building the cycle the smallest vertex from the part with $n$ elements. In the case that $m=n$, let us instead simply use element $1$. This gives us an unambiguous way of selecting which element is used as our reference point. and specifically does so in a way that makes it so that the part to which it belongs is of size $n$ and the other is of size $m$.

So, building our cycle, we start with the selected element. Choose which element from the other part comes after. We have $k$ choices. Then choose which element from the first part comes next, we have $k-1$ choices. Choose what comes after that, we have $k-1$ choices, and so on going back and forth between the two parts building the cycle out. This gives $k!(k-1)!$ ways to build out the cycle. Recognize again that we doublecounted the number of cycles because had we made the same decisions but in the reverse order it would have been the same overall result.

This gives $\binom{n}{k}\binom{m}{k}\frac{k!(k-1)!}{2}$

Recognize that in the case of $k=2$ this does indeed simplify as $\binom{n}{2}\binom{m}{2}\frac{2!(2-1)!}{2}=\binom{n}{2}\binom{m}{2}\frac{2\cdot 1}{2}=\binom{n}{2}\binom{m}{2}$

Final Takeaways... Determine a way to unambiguously count the cycles with as convenient an approach as possible that avoids overcounting when possible. A good way to do that is to pick reference points and determine how to arrange things around that reference point. Try to understand what each term in the final expressions represents in terms of decisions made in the counting process and whether those decisions determine a final arrangement or not or if there is missing information.

| cite | improve this answer | |
  • $\begingroup$ Thankyou so much for the detailed explanation, i dont't know what is the theory behind it so didn't understand how to get the formula, sometimes its hard to find exact resources that explain the theory behind some problems.. Thankyou! $\endgroup$ – fiksx Nov 21 '19 at 15:05

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.