Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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')$.
