# Probability of a double cycle in cuckoo graph

I have read Chater 17. Balanced Allocations and Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got stuck with a problem.

We have $$m$$ elements and $$n$$ buckets. Each element is hashed into two random buckets (we assume that two our hash functions are completely random). If each bucket corresponds to a vertex and each element corresponds to an edge. Then we have a random graph with $$n$$ vertices and $$m$$ edges. Loops and multi-edges are allowed.

I don't understand how to get the probability to reconstruct the whole cuckoo hash table. We reconstruct (reinsert all elements with new hash functions) a cuckoo hash table when a connected component has a double cycle. We can calculate probability that after inserting an element a double cycle occurs. This probability is $$\mathcal{O}(1/n^2)$$. To prove this, we consider the situation when the last inserted element creates a double cycle on exactly $$k$$ elements. Then before the insertion there were $$k$$ edges among these $$k$$ vertices. There are $${n}\choose{k}$$ ways of choosing these vertices, and $${m}\choose{k}$$ ways of choosing the items that correspond to the edges. Then the authors write the following sentence which I don't understand but I think it's kind of crucial:

After adding the new edge for the inserted item, the k + 1 edges must form a spanning tree, as well as two additional edges.

Don't $$k + 1$$ edges suppose to form double cycle not a spanning tree? Wasn't the spanning tree formed even before the insertion since we had $$k$$ vertices and $$k$$ edges among them? Also I don't understand why two additional edges must form a spanning tree and how is this fact connected to what we want to prove at all?

Next, the authors write the formula for probability we want to calculate:

$${n}\choose{k}$$ $${m}\choose{k}$$ $$k^{k - 2}$$ $${k + 1}\choose{2}$$ $$(k - 1)! \cdot \dots$$.

This formula isn't complete but my question about this part. Here $$k^{k - 2}$$ -- the number of trees on $$k$$ vertices, $$(k-1)!$$ -- the number of ways to map $$k-1$$ elements into $$k-1$$ edges. I don't understand the term $${k + 1}\choose{2}$$. Why do we choose $$2$$ edges from $$k + 1$$? Shouldn't we choose only one edge from $$k$$ edges? My point is that $$k - 1$$ edges form a spanning tree on $$k$$ vertices and one remaining edge as well as the edge that corresponds to the new item should form two cycles. Then we can choose the remaining edge in $$k$$ ways. I think the formula should be:

$${n}\choose{k}$$ $${m}\choose{k}$$ $$k^{k - 2}$$ $$k$$ $$(k - 1)! \cdot \dots$$.

Could you please explain me the details. May be I don't understand something?

Thank you!