# What are the number of 4 cycles in the Complete Bipartite graph?

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

-

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