<p>No.</p>

<p>Construction: Take two copies of $K_{3,3}$, one with the nodes $\{a,b,c\} \cup \{a&#39;,b&#39;,c&#39;\}$ and the other one with the nodes $\{d,e,f\} \cup \{d&#39;,e&#39;,f&#39;\}$. Remove the edges $(c,c&#39;)$ and $(d,d&#39;)$. Add the edges $(c,d&#39;)$ and $(d,c&#39;)$.</p>

CC BY-SA 3.0
2012-04-30T03:48:11.403Z
Thank you for finding this. For the record, I count 6 matchings that include (a,a), and 4 matchings that include (c,d').
sd234
CC BY-SA 3.0
2012-04-30T00:28:09.093Z
2012-04-30T00:28:09.093Z
Jukka Suomela
<p>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?</p>

<p>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?</p>

<graph-theory><co.combinatorics><graph-algorithms><randomness><matching>
In a random perfect matching of a regular bipartite graph, are all edges equally probable?
sd234
# In a random perfect matching of a regular bipartite graph, are all edges equally probable?

(Asked by: username_0 on 2012-04-29)

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?

**Tags:** graph-theory, co.combinatorics, graph-algorithms, randomness, matching

---

## 1 answers

### Answer by username_1 on 2012-04-30. Score: 12 | Accepted answer

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

> **Comments:**
> **username_0**: Thank you for finding this. For the record, I count 6 matchings that include (a,a), and 4 matchings that include (c,d').  

---

