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.

The question I have is: How many cycles of Length 4 are there in a Complete Bipartite graph in $K_{n,n}$? I can see there is 1 distinct cycle in $K_{2,2}$ but after that I can't seem to get it straight. I think I can see 4 distinct 4 cycles in $K_{3,3}$ but am not sure as I keep losing track of which I have counted. Thus I can't get past that to see a relationship and work from there. Any ideas?

Thanks,

Brian

share|improve this question

1 Answer 1

HINT: Let $V_0$ and $V_1$ be the two parts of $K_{n,n}$, so that each consists of $n$ vertices. Every $4$ cycle contains two vertices from $V_0$ and two from $V_1$. Suppose that you pick $v_0,v_1\in V_0$ and $u_0,u_1\in V_1$, where $v_0\ne v_1$ and $u_0\ne u_1$. They and their connecting edges form a little $K_{2,2}$, which indeed has one $4$-cycle. Thus, $K_{n,n}$ has exactly as many $4$-cycles as there are ways to pick two vertices from $V_0$ and two from $V_1$.

  • How many ways are there to choose two vertices from the $n$ in $V_0$?
  • How many ways are there to choose two vertices from the $n$ in $V_0$?
  • How do you combine those two numbers to get the answer?
share|improve this answer
    
Well, there are $_n$C$_2$ ways to choose vertices in $V_0$. It seems that those in $V_1$ should be repeats of those in $V_0$ so we wouldn't count those. When I try with 6 total vertices, it looks like there are 2 ways to chose $v_0 \in V_0$, and after all the cycles are drawn for that, there are 2 edges missing from the 9 edges between the 6 vertices. Adding in these two edges complete 1 cycle. So there would be a total of 3 cycles (Not 4 as I previously thought). So all in all there seem to be $_n$C$_2$ cycles (I am guessing for n vertices which is V/2 where V is the total vertices)? –  Relative0 Apr 4 '13 at 4:38
    
@user1922184: There are indeed $\binom{n}2$ ways to choose two vertices from $V_0$. I don’t understand your next comment: the vertices in $V_1$ are independent of those in $V_0$. Given a pair of vertices in $V_0$, you can combine them with any pair from $V_1$ to get a cycle, and all of those cycles are distinct. With $n=3$ there are $9$ $4$-cycles, not $3$. –  Brian M. Scott Apr 4 '13 at 4:42

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.