Consider the bipartite perfect matching problem Let the Wome

Consider the bipartite perfect matching problem. Let the Women be Ann, Beth, Christine, Dannie, live, Fran, and Georgette. Let the Men be Adam, Bob, Carl, Duarte, Ed, Ferdinand, Gabriel, Henry, and Isaac. Assume all the women like Carl, Gabriel, and Isaac. In addition, Ann likes Duarte; Beth and Christine like Adam; Dannie likes Adam, Bob, and Carl; Is there a perfect matching in this ease? If there is, give a perfect matching that marries all the women; It there is no perfect matching, give a set of women that violate Hall\'s condition, that is give a set of Women X such that collectively they like fewer men than the number of women in X. Prove that in a bipartite graph with vertex classes X and Y, every path from a vertex in X to a vertex in Y has odd length.

Solution

4. There is no perfect matching for all women . Here is the list :

Ann - Duarte

Beth - Adam ( Can be Christine to Adam )

Dannie - Bob

X ( List of remaining Women ) : Christine , Eve , Fran , Georgette

List of men liked by all :Carl , Gabriel , Issac

X violates Hall\'s condition