2
$\begingroup$

Here I'm considering the version of the marriage problem in which there can be more boys than girls.

Suppose there are two sets, one of boys and one of girls, the two satisfying Hall's condition for each girl being able to find a husband. Take a particular boy X liked by at least one girl. Why can we arrange the marriages in such a way that the boy is given a wife?

I'm able to prove this in the case in which there is at least one girl who likes no one but X. Then we can marry the two. Let's take a $k$-element subset of the set of the remaining girls. Then the girls know at least $k$ guys together. If they know at least $k+1$ guys, then even if X is among them, we can remove him leaving $k$ guys and not harming Hall's condition. If they know exactly $k$ guys and $X$ is not among them, the girls are fine. Suppose they know exactly $k$ guys and one of them is X. Then if we add X's new wife to them, together they still know $k$ guys, even though there are $k+1$ of them, which contradicts the assumption. Therefore, in this case, we can marry every one of the remaining girls by Hall's theorem.

So I can assume that every girl likes some boy other than X. But I don't see that this solves the problem for me.

$\endgroup$
2
$\begingroup$

Take any maximum matching $M$ and a boy $b$. If $b$ is saturated by $M$ then there is nothing to prove. Suppose $b$ is not saturated by $M$ and let $a$ be a neighbour of $b$. Since $M$ is of maximum size it must be the case that $ab'\in M$ for some $b'\in V(G)$. Then $M'=(M\setminus\{ab'\})\cup\{ab\}$ is a maximum matching saturating $b$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.