I need the number of perfect matchings in a complete bipartite graph, such that no edge is repeated in other perfect matchings. For example consider a bipartite graph with $n=6$, the complete graph with the three perfect matchings is given. No edge is repeated here. I know that the answer is $n/2$. But how to prove it?
Best Answer
We can reason this way. After we have found another perfect matching, we remove all the edges of this matching from our graph. We will obtain a new regular bipartite graph for which we can use this statement. After that we repeat the above process. It is clear that the process will end when all the edges are exhausted. As a result, we will get exactly $n/2$ of perfect matchings which have no edges repeated.