6
$\begingroup$

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?

$\endgroup$
12
$\begingroup$

No.

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')$.

$\endgroup$
  • 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$ – srd Apr 30 '12 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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