- #1

- 76

- 0

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: