How many subgraphs of $K_{9,9}$ are isomorphs of $C_6$?

Question

I approached this problem the following (apparently incorrect) way: In $K_{9,9}$, there are 18 vertices, so 18 choices for a starting point. From there, since the graph is bipartite, whichever "side" we start on, we must pick one of the 9 points on the other side. Then, we must pick one of the 8 remaining points on our side, then again one of 8 on the other side, etc., flip-flopping between the sides, until we get to the point where we have to go back to our starting point. By the multiplication principle, this gives me $$(18)(9)(8)(8)(7)(1)=72576$$But the correct answer is apparently $$(nCr(9,3))^2 \times 6=42336$$. What's wrong with my reasoning, and what's right about the correct one?

Answer 1

First of all, in your reasoning, there has to be one more $7$. So the product looks like $18\cdot9 \cdot8 \cdot8 \cdot7 \cdot7$. And only then an edge goes to the very first vertex.

Second, you overcount each cycle $12$ times in this calculation. Imagine you chose the vertices 1-2-3-4-5-6 and made a cycle in that order. But what if you start with the vertex 2 and make a cycle 2-3-4-5-6-1? It is the same cycle! So you should divide this product by $6$. But that’s not all! What if you pick the vertices in the following order: 6-5-4-3-2-1? Again, this is the same cycle! So you should divide your product by $6\cdot2=12$ to get the right answer.

$\binom93^2\cdot 6$ gives the same answer. $\binom93$ is the number of ways to choose $3$ vertices from one part, and the same number of ways to choose $3$ vertices from the other part of the graph. These three vertices can be joined in a cycle in $6$ ways. Indeed, let 1, 2, 3 be the vertices from one part, a, b, c from the other. We can WLOG assume that vertices 1, 2, 3 go in cycle in that order. Now we have $3$ choices, what two vertices from a, b, c will be next to the vertex 1 and $2$ choices in what order:

$$a1b, b1a, a1c, c1a, b1c, c1b$$

So the answer is $$\frac{18\cdot9 \cdot8 \cdot8 \cdot7 \cdot7}{12}=\binom93^2\cdot 6=42336.$$