I'm supposed to show that the marriage problem has a solution if every man is friends with exactly r women, and every women is friends with exactly r men.(adsbygoogle = window.adsbygoogle || []).push({});

I rewrote this problem in the language of transversals. I defined sets

[tex]S_i = \{ j | (i,j) \in E \}[/tex] in which E is the set of branches of the bipartite graph of the problem. It's obvious that every set [tex]S_i[/tex] has exactly r elements and that every element in {1,...,n} appears exactly r times in the collection of all these sets. To show that the mariage problem has a solution I must show that the collection [tex](S_1,S_2,\cdots,S_n)[/tex] is a transversal. And this is where I get stuck! :( Or is it really just so simple that it is too simple to see the solution? :uhh:

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Marriage problem

**Physics Forums | Science Articles, Homework Help, Discussion**