Consider a d-regular bipartite graph G, for d>=1. Obviously, G contains a perfect matching. Consider a perfect matching M in G chosen uniformly at random from all perfect matchings in G. Is it the case that, for arbitrary edges e and e', the probability e is in M is the same as the probability e' is in M?

Stated differently, I am asking the following: Is it the case that, for an edge e of a regular bipartite graph G, the number of perfect matchings that include e does not depend on e?


1 Answer 1



Construction: Take two copies of $K_{3,3}$, one with the nodes $\{a,b,c\} \cup \{a',b',c'\}$ and the other one with the nodes $\{d,e,f\} \cup \{d',e',f'\}$. Remove the edges $(c,c')$ and $(d,d')$. Add the edges $(c,d')$ and $(d,c')$.

  • 1
    $\begingroup$ Thank you for finding this. For the record, I count 6 matchings that include (a,a), and 4 matchings that include (c,d'). $\endgroup$
    – sd234
    Commented Apr 30, 2012 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.