# Clarifying a proof of Hall's Marriage Theorem

Well, i tried hard to read the converse of the proof and i guess they are using some so-called procedure and tricks to make the proof work. However i can't figure out how it works. Can someone show how the tricks work and explain why it works? thx in advance for your help.

Edited: What i am confused with is starting from the sentence in the proof of the converse "As in the previous example, let girl $m+1$ may personally only know boys.......I don't quite understand they way it prove it with that method.

-
Can you be more specific? What exactly are you confused about? – Qiaochu Yuan Feb 7 '12 at 8:50
related : math.stackexchange.com/q/45565/15660 – pedja Feb 7 '12 at 8:57
In my view this is an awful proof. It uses a steam engine instead the power of induction. – Christian Blatter Feb 7 '12 at 9:20
To Qiaochu Yuan:I have already edited what i am confused! – Mathematics Feb 7 '12 at 15:47
For accessibility and SEO, latexify the image. pastie.org/3338021 is a start; someone take over, please. – msh210 Feb 8 '12 at 0:06

The key points are:

• The hostess of the party is not engaged (yet)
• The hostess knows some boys (at least one from the question) and invites them
• Apart from the hostess, girls are only invited by their fiancés
• Boys are only invited by girls who know them and are the hostess or already invited, so are not invited by their fiancées
• At some stage there are at least as many boys as girls, as from the question a group of girls know at least as many boys
• Since all but one of the girls are engaged and their fiancés are at the party, at least one of the boys is not engaged; concentrate on one of them
• This unengaged boy knows at least one girl (engaged or the hostess) at the party since he was invited, so he can dance with a girl who invited him and he knows, and does
• That engaged girl's fiancé knows at least one other girl (engaged or the hostess) at the party since he was invited before the unengaged boy, so he can dance with a girl who invited him and he knows, and does
• That engaged girl's fiancé knows at least one other girl (engaged or the hostess) at the party since he was invited before the his fiancée's dancing partner, so he can dance with a girl who invited him and he knows, and does
• The pattern continues back up the invitation chain until a boy who was invited originally by the hostess dances with her
• Those of the original $m$ engaged girls and $m$ engaged boys not dancing (or not at the party) are all engaged pairs
• Those dancing can break their existing engagements and become engaged to their dancing partners
• So $m+1$ girls can find husbands from boys they know, proving the inductive step.
• So by induction they can all find a marriage partner and live happily ever after.

Which of these statements is difficult to follow?

-
It is not difficult to understand the sentense,the point is ,is it always works? As the man who the girl know can be randomly chosen,what if a case there is only one distributing way to distribute the man among the woman?Is this method work too and is there any proof about this method? – Mathematics Feb 8 '12 at 5:23
@Mathematics: If there is only one way to reallocate the $m+1$ girls and boys into engaged pairs, this would mean that each boy at the party only received one invitation, and when choosing dancing partners each boy would only have one choice, but the method would still work. It will always work based on the supposition in the question. – Henry Feb 8 '12 at 7:44

Here are some basic concepts that may help. Relations are not always transitive, which is why we talk about closures. Connectivity in graph theory is also relevant.

-