Marriage Problem Every Man & Woman Friends w/ r People

[Pietjuh]

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.

I rewrote this problem in the language of transversals. I defined sets
S_i = \{ j | (i,j) \in E \} in which E is the set of branches of the bipartite graph of the problem. It's obvious that every set S_i 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 (S_1,S_2,\cdots,S_n) 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?

 

[mathmike]

I think you need to take the negative of the woman and add it to the positve of the man and then intergate it with the limits of logic

 

[Antiphon]

I think you need to take the negative of the woman and add it to the positve of the man and then intergate it with the limits of logic

I fear the result will be complex .

Jokes aside, please state the entire marriage problem for those of us
who aren't familiar with it.

 

[Pietjuh]

Ok here's the explanation of the marriage theorem:
Let's say we've got a bipartite graph G = (V,E) in which V = V_1 U V_2
The vertices in V_1 are called men, and those in V_2 are called women.
The marriage problem is the problem of finding a complete matching in this bipartite graph. So you need to match every man with every women, such that no man or woman is matched more than 1 time.

The marriage theorem of Hall says this problem has a solution if for every k-tuple of men, the number of women they are willing to have a relationship with is larger or equal than k.

So in my problem you don't have a problem if k <= r, because if you take a k-tuple with k<=r the number of people they are willing to have a relationship with is at least r >=k. All I need to show is that for every k-tuple with k > r you can always find at least k friends.

 

[Antiphon]

I think I'm missing something. You can match everyone (and trivially) if and only if
the number of men is equal to the number of women. No?