How many different Hamilton cycles are there in the complete

How many different Hamilton cycles are there in the complete bipartite graph Kn,n, where n 3?

Solution

The complete bipartite graph Km,n is defined by taking two disjoint sets, V1 of size m and V2 of size n, and putting an edge between u and v whenever u V1 and v V2.

Every cycle in a bipartite graph is even and alternates between vertices from V1 and V2. Since a Hamilton cycle uses all the vertices in V1 and V2, we must have m = |V1| = |V2| = n. Suppose that Kn,n has partite sets V1 = {v1, . . . , vn} and V2 = {w1, . . . , wn}. Since viwj is an edge of Kn,n for every 1 i, j n, we see that v1, w1, v2, w2, . . . , vn, wn is a Hamiltonian cycle (note that wnv1 is an edge).