Graph Theory – Disjoint Perfect Matchings in Complete Bipartite Graph

co.combinatoricsgraph theorymatching-theoryperfect-matchings

Let $K_{n,n}$ be a complete bipartite graph with two parts $\{u_1,u_2,\ldots,u_n\}$ and $\{v_1,v_2,\ldots,v_n\}$, and let $K^-_{n,n}$ be the graph derived from $K_{n,n}$ by delete a perfect matching $\{u_1v_1,u_2v_2,\ldots,u_nv_n\}$.

Since $K^-_{n,n}$ is now $(n-1)$-regular, it has $n-1$ disjoint perfect matchings. My question is whether the edges of $K^-_{n,n}$ with $n\geq 4$ can be decomposed into $n-1$ disjoint perfect matchings in such a way that in each matching $M$, if $u_iv_j\in E(M)$ then $v_iu_j\not\in E(M)$.

Best Answer

The answer is that this is possible for all $n>4$.

Your question is equivalent to asking whether there exists a unipotent Latin square $L$ of order $n$ with $L_{ij}\ne L_{ji}$ for $i\ne j$. The equivalence is obtained by using $L_{ij}$ to record the index of the matching that contains the edge $u_i v_j$ (and putting $L_{ii}=n$ for each $i$).

The existence of such a Latin square follows from a stronger property. It is a theorem (collectively due to the work of Kotzig, McLeish, Turgeon and others) that for all $n\notin\{2,4\}$ there exists a Latin square of order $n$ that has no intercalates (an intercalate is a $2\times2$ submatrix that is itself a Latin square). This property of Latin squares is called $N_2$ in the literature.

If you permute the rows of any $N_2$ Latin square you can make every symbol on the main diagonal equal to $n$. You then have what you need.

Related Question