Determine the number of distinct cycle subgraphs of $K_(3,3)$

Question

I have tried $~^3 C_2\cdot ~^3 C_2 + ~^3 C_3 \cdot ~^3 C_ 3 + \frac{3!3!}{6}$, which equals to 16, but I'm not sure whether it is correct.

Answer 1

A bipartite graph only has even cycles with the same number of vertices in each partition.

If all 6 vertices are in the cycle, the cycle length is 6 by handshaking lemma (sum of degrees, $6\cdot2$, is 2 times the edges). 2-cycles are not possible for a simple graph and so the only possible cycles are 4-cycles and 6-cycles, corresponding to 2 and 3 vertices in each partition respectively.

For 4-cycles, there are $\binom{3}{2}\cdot\binom{3}{2}$ of them. For 6-cycles, there are $\frac{3\cdot2\cdot2}{2}$ of them.

There are in total 15 cycles.

From your expression, it seems like you assumed an 8-cycle is possible, which is not the case.