Using Hall's Theorem to show something.

Question

Suppose that there are five young women and five young men on an island. Each man is willing to marry some of the women on the island and each woman is willing to marry any man who is willing to marry her. Suppose that Sandeep is willing to marry Tina and Vandana; Barry is willing to marry Tina, Xia, and Uma; Teja is willing to marry Tina and Zelda; Anil is willing to marry Vandana and Zelda; and Emilio is willing to marry Tina and Zelda. Use Hall’s theorem to show there is no matching of the young men and young women on the island such that each young man is matched with a young woman he is willing to marry.

The thing about this problem is that it's not a typical Hall's theorem problem. Can someone please explain how Hall's theorem is being applied here? Maybe I don't understand Hall's theorem right, as what I do is simply count how many edges there are.

Answer 1

Use a choice tree. Start with one of the boys who likes the least number of girls. The first level of the tree represent his choice; each branch is for one girl from his preferences. Then the next level of the tree is for the next boy and his choices - but he cannot choose a girl who has been chosen on a directly-earlier branch of the tree. Continue in this fashion until you reach a point where there is at least one boy who cannot be matched with any of their preferences. If all branches end in such a way, then you prove that no possible choices of the first boy allow for every other boys to also have their choice. And done.

Answer 2

In the bipartite graph, the (male) vertices $S$, $B$, $Te$, $A$, and $E$ have (female) neighbor sets $\{Ti,V\}$, $\{Ti,X,U\}$, $\{Ti,Z\}$, $\{V,Z\}$, and $\{Ti,Z\}$, respectively. For the subset $\{S,Te,A,E\}$, the neighbor set is $\{Ti,V,Z\}$. Since $|\{S,Te,A,E\}|=4\gt3=|\{Ti,V,Z\}|$, Hall's marriage theorem says there can be no perfect match. That is, Hall's theorem says that there is a perfect match from $X$ to $Y$ if and only if for all subsets of $X$, the neighbor set is at least as large.

Minor aside: To my knowledge, "Teja" is mainly a girl's name. See for example, the mathematical artist Teja Krasek.